The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Multi-dimensional range queries in sensor networks
Abstract
In many sensor networks, data or events are named by attributes. Many of these attributes have scalar values, so one natural way to query events of interest is to use a multi-dimensional range query. An example is: "List all events whose temperature lies between 50° and 60°, and whose light levels lie between 10 and 15." Such queries are useful for correlating events occurring within the network.In this paper, we describe the design of a distributed index that scalably supports multi-dimensional range queries. Our distributed index for multi-dimensional data (or DIM) uses a novel geographic embedding of a classical index data structure, and is built upon the GPSR geographic routing algorithm. Our analysis reveals that, under reasonable assumptions about query distributions, DIMs scale quite well with network size (both insertion and query costs scale as O(√N)). In detailed simulations, we show that in practice, the insertion and query costs of other alternatives are sometimes an order of magnitude more than the costs of DIMs, even for moderately sized network. Finally, experiments on a small scale testbed validate the feasibility of DIMs.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Chord: A scalable peer-to-peer lookup service for internet applications
Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., & Balakrishnan, H. (2001) · Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/383059.383071 · Cited by 9,623
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
GPSR: greedy perimeter stateless routing for wireless networks
Karp, B., & Kung, H. T. (2000) · Proceedings of the 6th annual international conference on Mobile computing and networking · doi:10.1145/345910.345953 · Cited by 7,050
R-trees: a dynamic index structure for spatial searching
Guttman, A. (1984) · Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 · doi:10.1145/602259.602266 · Cited by 6,580
A scalable content-addressable network
Ratnasamy, S., Francis, P., Handley, M., Karp, R., & Shenker, S. (2001) · Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/383059.383072 · Cited by 6,372
Directed diffusion: a scalable and robust communication paradigm for sensor networks
Intanagonwiwat, C., Govindan, R., & Estrin, D. (2000) · Proceedings of the 6th annual international conference on Mobile computing and networking · doi:10.1145/345910.345920 · Cited by 5,393
Self-citationApproximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
(1999) · Cited by 3,186
TAG: a Tiny AGgregation service for ad-hoc sensor networks
Madden, S., Franklin, M. J., Hellerstein, J. M., & Hong, W. (2002) · ACM SIGOPS Operating Systems Review · doi:10.1145/844128.844142 · Cited by 2,719
Self-citationFreenet: A Distributed Anonymous Information Storage and Retrieval System
Clarke, I., Sandberg, O., Wiley, B., & Hong, T. W. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44702-4_4 · Cited by 2,109
Cited by
Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards
Baronti, P., Pillai, P., Chook, V. W. C., Chessa, S., Gotta, A., & Hu, Y. F. (2007) · Computer Communications · doi:10.1016/j.comcom.2006.12.020 · Cited by 1,430
Mercury: supporting scalable multi-attribute range queries
Bharambe, A. R., Agrawal, M., & Seshan, S. (2004) · Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1015467.1015507 · Cited by 675
Information fusion for wireless sensor networks: Methods, models, and classifications
Nakamura, E. F., Loureiro, A. A. F., & Frery, A. C. (2007) · ACM Computing Surveys · doi:10.1145/1267070.1267073 · Cited by 537
Geographic routing made practical
Kim, Y.-J., Govindan, R., Karp, B., & Shenker, S. J. (2005) · doi:10.5555/1251203.1251219 · Cited by 373
Self-citationGeospatial Cyberinfrastructure: Past, present and future
Yang, C., Raskin, R., Goodchild, M., & Gahegan, M. (2010) · Computers, Environment and Urban Systems · doi:10.1016/j.compenvurbsys.2010.04.001 · Cited by 350
Metadata
- Authors
- Li, X., Kim, Y. J., Govindan, R., & Hong, W.
- Venue
- Proceedings of the 1st international conference on Embedded networked sensor systems
- Publisher
- ACM
- Published
- 2003-11-05
- Pages
- 63-75
- OpenAlex
- W2130029160
- Cited by
- 387
- References
- 15
- FWCI
- 18.84
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Multi-dimensional range queries in sensor networks. https://app.cochat.ai/papers/10.1145/958491.958500
- The paper
- Li, X., Kim, Y. J., Govindan, R., & Hong, W. (2003). Multi-dimensional range queries in sensor networks. Proceedings of the 1st international conference on Embedded networked sensor systems. https://doi.org/10.1145/958491.958500
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.