Skip to main content

A sampling-based approach to optimizing top-k queries in sensor networks

Publication ,  Journal Article
Silberstein, A; Braynard, R; Ellis, C; Munagala, K; Yang, J
Published in: Proceedings - International Conference on Data Engineering
October 17, 2006

Wireless sensor networks generate a vast amount of data. This data, however, must be sparingly extracted to conserve energy, usually the most precious resource in battery-powered sensors. When approximation is acceptable, a model-driven approach to query processing is effective in saving energy by avoiding contacting nodes whose values can be predicted or are unlikely to be in the result set. To optimize queries such as top-k, however, reasoning directly with models of joint probability distributions can be prohibitively expensive. Instead of using models explicitly, we propose to use samples of past sensor readings. Not only are such samples simple to maintain, but they are also computationally efficient to use in query optimization. With these samples, we can formulate the problem of optimizing approximate top-k queries under an energy constraint as a linear program. We demonstrate the power and flexibility of our sampling-based approach by developing a series of top-k query planning algorithms with linear programming, which are capable of efficiently producing plans with better performance and novel features. We show that our approach is both theoretically sound and practically effective on simulated and real-world datasets. © 2006 IEEE.

Duke Scholars

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

October 17, 2006

Volume

2006

Start / End Page

68
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Silberstein, A., Braynard, R., Ellis, C., Munagala, K., & Yang, J. (2006). A sampling-based approach to optimizing top-k queries in sensor networks. Proceedings - International Conference on Data Engineering, 2006, 68. https://doi.org/10.1109/ICDE.2006.10
Silberstein, A., R. Braynard, C. Ellis, K. Munagala, and J. Yang. “A sampling-based approach to optimizing top-k queries in sensor networks.” Proceedings - International Conference on Data Engineering 2006 (October 17, 2006): 68. https://doi.org/10.1109/ICDE.2006.10.
Silberstein A, Braynard R, Ellis C, Munagala K, Yang J. A sampling-based approach to optimizing top-k queries in sensor networks. Proceedings - International Conference on Data Engineering. 2006 Oct 17;2006:68.
Silberstein, A., et al. “A sampling-based approach to optimizing top-k queries in sensor networks.” Proceedings - International Conference on Data Engineering, vol. 2006, Oct. 2006, p. 68. Scopus, doi:10.1109/ICDE.2006.10.
Silberstein A, Braynard R, Ellis C, Munagala K, Yang J. A sampling-based approach to optimizing top-k queries in sensor networks. Proceedings - International Conference on Data Engineering. 2006 Oct 17;2006:68.

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

October 17, 2006

Volume

2006

Start / End Page

68