research-article

Microsearch: A search engine for embedded devices used in pervasive computing

Authors:

Qun LiAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 9, Issue 4

Article No.: 43, Pages 1 - 29

https://doi.org/10.1145/1721695.1721709

Published: 06 April 2010 Publication History

Abstract

In this article, we present Microsearch, a search system suitable for embedded devices used in ubiquitous computing environments. Akin to a desktop search engine, Microsearch indexes the information inside a small device, and accurately resolves a user's queries. Given the limited hardware, conventional search engine design and algorithms cannot be used. We adopt Information Retrieval (IR) techniques for query resolution, and proposed a new space-efficient top-k query resolution algorithm. A theoretical model of Microsearch is given to better understand the trade-offs in design parameters. Evaluation is done via actual implementation on off-the-shelf hardware.

References

[1]

Abowd, G. D., Atkeson, C. G., Hong, J., Long, S., Kooper, R., and Pinkerton, M. 1997. Cyberguide: A mobile context-aware tour guide. Wireless Networks 3, 5, 421--433.

Digital Library

[2]

Apple. 2007. http://www.apple.com/macosx/features/spotlight/.

[3]

Baeza-Yates, R., Dupret, G., and Velasco, J. 2007. A study of mobile search queries in Japan. In Proceedings of the World Wide Web Conference: Query Log Analysis: Social and Technological Challenges (WWW'07). ACM, New York.

[4]

Beagle. 2007. http://beagle-project.org/main page.

[5]

Chen, J., Diekema, A., Taffet, M. D., McCracken, N. J., Ozgencil, N. E., Yilmazel, O., and Liddy, E. D. 2001. Question answering: CNLP at the TREC-10 question answering track. In Proceedings of the Text Retrieval Conference. TREC, Gaithersburg, MD.

[6]

Cheverst, K., Davies, N., Mitchell, K., and Friday, A. 2000a. Experiences of developing and deploying a context-aware tourist guide: The guide project. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom'00). ACM, New York, 20--31.

Digital Library

[7]

Cheverst, K., Davies, N., Mitchell, K., Friday, A., and Efstratiou, C. 2000. Developing a context-aware electronic tourist guide: Some issues and experiences. In Proceedings of the SIG Conference on Human Factors in Computing Systems (CHI'00). ACM, New York, 17--24.

Digital Library

[8]

Church, K., Smyth, B., Cotter, P., and Bradley, K. 2007. Mobile information access: A study of emerging search behavior on the mobile internet. ACM Trans. Web 1, 1, 4.

Digital Library

[9]

Company, A. 2008. Yaffs: yet another flash file system. In http:/www.yaffs.net/.

[10]

Dai, H., Neufeld, M., and Han, R. 2004. Elf: An efficient log-structured flash file system for microsensor nodes. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys'04). ACM, New York, 176--187.

Digital Library

[11]

Faloutsos, C. 1985. Access methods for text. ACM Comput. Surv. 17, 1.

Digital Library

[12]

Faloutsos, C. and Oard, D. W. 1995. A survey of information retrieval and filtering methods. Tech. rep. CS-TR-3514, University of Maryland, College Park.

Digital Library

[13]

Frakes, W. B. and Baeza-Yates, R. A., Eds. 1992. Information retrieval: Data structures and algorithms. Prentice-Hall, Upper Saddle River, NJ.

Digital Library

[14]

French, J. C., Powell, A. L., Callan, J. P., Viles, C. L., Emmitt, T., Prey, K. J., and Mou, Y. 1999. Comparing the performance of database selection algorithms. In Proceedings of the Annual Conference on Research and Development in Information Retrieval. ACM, New York.

Digital Library

[15]

Gal, E. and Toledo, S. 2005a. Algorithms and data structures for flash memories. ACM Comput. Surv. 37, 2.

Digital Library

[16]

Gal, E. and Toledo, S. 2005b. A transactional flash file system for microcontrollers. In Proceedings of the Annual Conference on Annual Technical Conference (ATEC'05). USENIX, Berkeley, CA, 7.

Digital Library

[17]

Google. 2007. http://www.desktop.google.com.

[18]

Kamvar, M. and Baluja, S. 2006. A large scale study of wireless search behavior: Google mobile search. In Proceedings of the Conference on Human Factors in Computing Systems (CHI'06). ACM, New York, 701--709.

Digital Library

[19]

Kobayashi, M. and Takeda, K. 2000. Information retrieval on the Web. ACM Comput. Surv. 32, 2, 144--173.

Digital Library

[20]

Logitec. 2004. http://www.logitech.com.

[21]

Mathur, G., Desnoyers, P., Ganesan, D., and Shenoy, P. 2006a. Capsule: an energy-optimized object storage system for memory-constrained sensor devices. In Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys'06). ACM, New York, 195--208.

Digital Library

[22]

Mathur, G., Desnoyers, P., Ganesan, D., and Shenoy, P. 2006b. Ultra-low power data storage for sensor networks. In Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN'06). ACM, New York, 374--381.

Digital Library

[23]

Nachman, L., Kling, R., Adler, R., Huang, J., and Hummel, V. 2005. The intel Rmote platform: A bluetooth-based sensor network for industrial monitoring. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN'05). IEEE, Los Alamitos, CA, 61.

Digital Library

[24]

Pucheral, P., Bouganim, L., Valduriez, P., and Bobineau, C. 2001. Picodbms: Scaling down database techniques for the smartcard. VLDB J. 10, 2-3, 120--132.

Digital Library

[25]

Rekimoto, J., Ayatsuka, Y., and Hayashi, K. 1998. Augment-able reality: situated communication through physical and digital spaces. In Proceedings of the 2nd International Symposium on Wearable Computers. IEEE, Los Alamitos, CA, 68--75.

Digital Library

[26]

Shah, C. and Croft, W. B. 2004. Evaluating high accuracy retrieval techniques. In Proceedings of the 27th Annual International Conference on Research and Development in Information Retrieval (SIGIR'04). ACM, New York, 2--9.

Digital Library

[27]

Starner, T., Kirsch, D., and Assefa, S. 1997. The locust swarm: An environmentally-powered, network-less location and messaging system. In Proceedings of the 1st International Symposium on Wearable Computers. IEEE, Los Alamitos, CA, 169--170.

Digital Library

[28]

Tan, C. C., Sheng, B., Wang, H., and Li, Q. 2008. MicroSearch: When search engines meet small devices. In Proceedings of the 6th International Conference on Pervasive Computing. Springer, Berlin, 93--110.

Digital Library

[29]

Voorhees, E. M. 2001. Overview of the trec 2001 question answering track. In Proceedings of the 10th Text Retrieval Conference. TREC, Gaithersburg, MD, 42--51.

[30]

Wang, H., Sheng, B., and Li, Q. 2006. Elliptic curve cryptography based access control in sensor networks. Int. J. Sensor Networks.

Digital Library

[31]

Wang, H., Sheng, B., Tan, C. C., and Li, Q. 2007. WM-ECC: An Elliptic Curve Cryptography Suite on Sensor Motes. Tech. rep. WM-CS-2007-11, College of William and Mary, Computer Science, Williamsburg, VA.

[32]

Wang, H., Sheng, B., Tan, C. C., and Li, Q. 2008. Comparing symmetric-key and public-key based security schemes in sensor networks: A case study of user access control. In Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS'08). IEEE, Los Alamitos, CA, 11--18.

Digital Library

[33]

Wang, H., Tan, C. C., and Li, Q. 2008. Google: A search engine for physical world. In Proceedings of the IEEE Conference on Computer Communications. IEEE, Los Alamitos, CA, 1382--1390.

[34]

Woodhouse, D. 2001. Jffs: The journaling flash file system. In Proceedings of the Ottawa Linux Symposium.

[35]

Yap, K.-K., Srinivasan, V., and Motani, M. 2005. Max: Human-centric search of the physical world. In Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SenSys'05). ACM, New York, 166--179.

Digital Library

[36]

Zeinalipour-Yazti, D., Lin, S., Kalogeraki, V., Gunopulos, D., and Najjar, W. A. 2005. Micro-hash: An efficient index structure for flash-based sensor devices. In Proceedings of the 4th Conference on File and Storage Technologies (FAST'05). USENIX, Berkeley, CA, 3.

Digital Library

Cited By

Ciortea AMayer SBienz SGandon FCorby O(2024)Autonomous search in a social and ubiquitous WebPersonal and Ubiquitous Computing10.1007/s00779-020-01415-128:1(259-272)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00779-020-01415-1
Rawassizadeh RRong Y(2023)ODSearchProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/35694886:4(1-25)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3569488
Tang JLu XXiang YShi CGu J(2023)Blockchain search engine: Its current research status and future prospect in Internet of Things networkFuture Generation Computer Systems10.1016/j.future.2022.08.008138(120-141)Online publication date: Jan-2023
https://doi.org/10.1016/j.future.2022.08.008
Show More Cited By

Index Terms

Microsearch: A search engine for embedded devices used in pervasive computing
1. Networks
  1. Network architectures

Recommendations

Microsearch: When Search Engines Meet Small Devices
Pervasive '08: Proceedings of the 6th International Conference on Pervasive Computing

In this paper, we present Microsearch, a search system suitable for small devices used in ubiquitous computing environments. Akin to a desktop search engine, Microsearch indexes the information inside a small device, and accurately resolves user ...
Identifying popular search goals behind search queries to improve web search ranking
AIRS'11: Proceedings of the 7th Asia conference on Information Retrieval Technology

Web users usually have a certain search goal before they submit a search query. However, many laypersons can't transform their search goals into suitable queries. Thus, understanding original search goals behind a query is very important for search ...
An Empirical Evaluation on Semantic Search Performance of Keyword-Based and Semantic Search Engines: Google, Yahoo, Msn and Hakia
ICIMP '09: Proceedings of the 2009 Fourth International Conference on Internet Monitoring and Protection

This paper investigates the semantic search performance of search engines. Initially, three keyword-based search engines (Google, Yahoo and Msn) and a semantic search engine (Hakia) were selected. Then, ten queries, from various topics, and four phrases,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 9, Issue 4

March 2010

438 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/1721695

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 06 April 2010

Accepted: 01 March 2009

Revised: 01 February 2009

Received: 01 May 2008

Published in TECS Volume 9, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Computer and Network Systems

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
518
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ciortea AMayer SBienz SGandon FCorby O(2024)Autonomous search in a social and ubiquitous WebPersonal and Ubiquitous Computing10.1007/s00779-020-01415-128:1(259-272)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00779-020-01415-1
Rawassizadeh RRong Y(2023)ODSearchProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/35694886:4(1-25)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3569488
Tang JLu XXiang YShi CGu J(2023)Blockchain search engine: Its current research status and future prospect in Internet of Things networkFuture Generation Computer Systems10.1016/j.future.2022.08.008138(120-141)Online publication date: Jan-2023
https://doi.org/10.1016/j.future.2022.08.008
Zhang HZhu LDai TZhang LFeng XZhang LZhang K(2023)Smart object recommendation based on topic learning and joint features in the social internet of thingsDigital Communications and Networks10.1016/j.dcan.2022.04.0259:1(22-32)Online publication date: Mar-2023
https://doi.org/10.1016/j.dcan.2022.04.025
Bouguettaya ASheng QBenatallah BNeiat AMistry SGhose ANepal SYao L(2021)An internet of things service roadmapCommunications of the ACM10.1145/346496064:9(86-95)Online publication date: 24-Aug-2021
https://dl.acm.org/doi/10.1145/3464960
Tang JZhou ZXue XWang G(2020)Using Collaborative Edge-Cloud Cache for Search in Internet of ThingsIEEE Internet of Things Journal10.1109/JIOT.2019.29463897:2(922-936)Online publication date: Mar-2020
https://doi.org/10.1109/JIOT.2019.2946389
Tang JXue XYangui SZhou Z(2020)Efficient Search for Moving Object Devices in Internet of Things Networks2020 IEEE International Conference on Web Services (ICWS)10.1109/ICWS49710.2020.00067(454-462)Online publication date: Oct-2020
https://doi.org/10.1109/ICWS49710.2020.00067
Zhang WSheng QMahmood ATran DZaib MHamad SAljubairy AAlhazmi ASagar SMa C(2020)The 10 Research Topics in the Internet of Things2020 IEEE 6th International Conference on Collaboration and Internet Computing (CIC)10.1109/CIC50333.2020.00015(34-43)Online publication date: Dec-2020
https://doi.org/10.1109/CIC50333.2020.00015
Rahman HHussain M(2020)A comprehensive survey on semantic interoperability for Internet of ThingsTransactions on Emerging Telecommunications Technologies10.1002/ett.390231:12Online publication date: 22-Dec-2020
https://dl.acm.org/doi/10.1002/ett.3902
Saputra YHua JWendt NJulien CRoman GTilevich E(2019)WarbleProceedings of the 6th International Conference on Mobile Software Engineering and Systems10.5555/3340730.3340755(128-139)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.5555/3340730.3340755
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents