TY - GEN
T1 - Hierarchical constraint satisfaction in spatial databases
AU - Papadias, Dimitris
AU - Kalnis, Panos
AU - Mamoulis, Nikos
PY - 1999
Y1 - 1999
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0032596639&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0032596639
SN - 0262511061
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 142
EP - 147
BT - Proceedings of the National Conference on Artificial Intelligence
PB - AAAI
T2 - Proceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99)
Y2 - 18 July 1999 through 22 July 1999
ER -