Title :
Shift Hashing for Memory-Constrained Applications
Author :
Deodhar, Sushamna ; Tharp, Alan L.
Author_Institution :
Dept. of Comput. Sci., North Carolina State Univ., Raleigh, NC, USA
Abstract :
Hardware innovations such as motes, RFIDs, embedded microprocessors, and wireless sensors have introduced a new set of wide-ranging applications for business, government, industry, and individuals. These applications include connected cities, smart homes and appliances, smart vehicles, improved security and surveillance, business integration and e-commerce to name a few. The real-time nature of these applications requires direct access to data and minimal response time from underlying hardware systems. This paper presents a new hashing method, Shift Hashing, which is an improvement over existing hashing schemes such as Tridirectional Computed Chaining, which reduce the direct access time by providing multi-way branching of individual probe chains. What is distinctive about Shift Hashing is that it not only allows faster access to data in most cases, but also eliminates the space requirement for storing links completely. There is no time-space tradeoff. Hence the method is suitable for applications in which space is quite limited and fast and real-time access is important. It is simple, easy to implement and its generality makes it very flexible to use. Storage efficiency is achieved by incorporating a link field in the key of the record by using bit shifting methods. The concept of using shifting to compute data rather than storing it may be applicable to other situations as well.
Keywords :
storage management; RFID; business integration; connected cities; direct access time; e-commerce; embedded microprocessor; hardware systems; memory-constrained application; multiway branching; probe chain; security; shift hashing; smart homes; smart vehicles; surveillance; tridirectional computed chaining; wireless sensor; Cities and towns; Communication system security; Government; Hardware; Intelligent sensors; Microprocessors; Radiofrequency identification; Smart homes; Technological innovation; Wireless sensor networks; Bit Shifting; Data Access Methods; Embedded Systems; Hashing; Minimal Response Time; Real-time Systems; Tridirectional Computed Chaining;
Conference_Titel :
Computer Software and Applications Conference, 2009. COMPSAC '09. 33rd Annual IEEE International
Conference_Location :
Seattle, WA
Print_ISBN :
978-0-7695-3726-9
DOI :
10.1109/COMPSAC.2009.77