Hierarchical constraint satisfaction in spatial databases

Dimitris Papadias; Panos Kalnis; Nikos Mamoulis

Hierarchical constraint satisfaction in spatial databases

Dimitris Papadias^*, Panos Kalnis, Nikos Mamoulis

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

9 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the National Conference on Artificial Intelligence
Publisher	AAAI
Pages	142-147
Number of pages	6
ISBN (Print)	0262511061
State	Published - 1999
Externally published	Yes
Event	Proceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99) - Orlando, FL, USA Duration: Jul 18 1999 → Jul 22 1999

Other

Other	Proceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99)
City	Orlando, FL, USA
Period	07/18/99 → 07/22/99

ASJC Scopus subject areas

Software

Cite this

@inproceedings{f57a26cd3ac341829e8af946c9753775,

title = "Hierarchical constraint satisfaction in spatial databases",

abstract = "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.",

author = "Dimitris Papadias and Panos Kalnis and Nikos Mamoulis",

year = "1999",

language = "English (US)",

isbn = "0262511061",

pages = "142--147",

booktitle = "Proceedings of the National Conference on Artificial Intelligence",

publisher = "AAAI",

note = "Proceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99) ; Conference date: 18-07-1999 Through 22-07-1999",

}

Papadias, D, Kalnis, P & Mamoulis, N 1999, Hierarchical constraint satisfaction in spatial databases. in Proceedings of the National Conference on Artificial Intelligence. AAAI, pp. 142-147, Proceedings of the 1999 16th National Conference on Artificial Intelligence (AAAI-99), 11th Innovative Applications of Artificial Intelligence Conference (IAAI-99), Orlando, FL, USA, 07/18/99.

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

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 -

Hierarchical constraint satisfaction in spatial databases

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this