Author name cluster

Dimitris Papadias

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

AAAI Conference 1999 Conference Paper

Hierarchical Constraint Satisfaction in Spatial Databases

Dimitris Papadias
Panos Kalnis
Nikos Mamoulis
Hong Kong University of Science
Technology

Several content-based queries in spatial databases and geographic information systems (GISs) can be modelled and processed as constraint satisfaction problems (CSPs). Regular CSP algorithms, however, work for main memory retrieval without utilizing indices to prune the search space. This paper shows how systematic and local search techniques can take advantage of the hierarchical decomposition of space, preserved by spatial data structures, to efficiently guide search. We study the conditions under which hierarchical constraint satisfaction outperforms traditional methods with extensive experimentation.

PDF Details

IJCAI Conference 1999 Conference Paper

Improving search using indexing: a study with temporal CSPs

Nikos Mamoulis
Dimitris Papadias

Most studies concerning constraint satisfaction problems (CSPs) involve variables that take values from small domains. This paper deals with an alternative form of temporal CSPs; the number of variables is relatively small and the domains are large collections of intervals. Such situations may arise in temporal databases where several types of queries can be modeled and processed as CSPs. For these problems, systematic CSP algorithms can take advantage of temporal indexing to accelerate search. Directed search versions of chronological backtracking and forward checking are presented and tested. Our results show that indexing can drastically improve search performance.

PDF

IJCAI Conference 1995 Conference Paper

Topological Inference

Michelangelo Grigni
Dimitris Papadias
Christos Papadimitriou

Geographical database systems deal with certain basic topological relations such as "A overlaps B" and "B contains C" between simply connected regions in the plane. It is of great interest to make sound inferences from elementary statements of this form. This problem has been identified extensively in the recent literature, but very limited progress has been made towards addressing the considerable technical difficulties involved. In this paper we study the computational problems involved in developing such an inference system. We point out that the problem has two distinct components that interact in rather complex ways: relational consistency, and planarity. We develop polynomial-time algorithms for several important special cases, and prove almost all the others to be NP-hard.

PDF