FSort: External Sorting on Flash-based Sensor Devices

Panayiotis Andreou, Orestis Spanos, Demetrios Zeinalipour-Yazti,

George Samaras, Panos K. Chrysanthis‡
Department of Computer Science, University of Cyprus, P.O. Box 20537, 1678 Nicosia, Cyprus
‡
Department of Computer Science, University of Pittsburgh, Pittsburgh, PA 15260, USA
{panic,cs05os1,dzeina,cssamara}@cs.ucy.ac.cy, [email protected]

ABSTRACT measurements locally at each sensor and transmit them to

In long-term deployments of Wireless Sensor Networks, it is the user only when requested. Such a scheme is particularly
often more efficient to store sensor readings locally at each favored because communication over the radio in a WSN is
device and transmit those readings to the user only when far more energy demanding than all other functions, such as
requested (i.e., in response to a user query). Many of the storage [26, 2, 1] and processing [13, 22, 24, 25].
techniques that collect information from a sensor network Although storing the data locally at each sensor is more ef-
require that the data is sorted on some attribute (e.g., range ficient than transmitting it continuously to a sink point, the
queries, top-k queries, join queries, etc.) Yet, the underlying storing process by itself raises some important challenges.
storage medium of these devices (i.e., Flash media) presents For instance when users perform range queries by a given
some unique characteristics which renders traditional disk- attribute, (e.g., “Find GPS locations where humidity is in
based sorting algorithms inefficient in this context. the range A to B”), then that requires that the data is se-
In this paper we devise the F Sort algorithm, an effi- quentially organized (i.e., sorted) by the humidity attribute
cient external sorting algorithm for flash-based sensor de- or that some access method that organizes the given at-
vices with a small memory footprint. F Sort minimizes the tribute sequentially (e.g., B + Tree) is available. Otherwise,
expensive write/delete operations of flash memory minimiz- the query will end up traversing a very large number of data
ing in that way the consumption of energy. In particular, pages incurring a large read cost. Notice that reading data
F Sort uses a top-down replacement selection algorithm in off the flash media in large quantities has a significant cost
order to produce sorted runs on flash media in a log-based in its own right. Another example where data needs to be
manner. Sorted runs are then recursively merged in order to sorted on flash is when a query aims to JOIN data under a
yield the sorted result. Our experimentation with real traces specific attribute. Such JOIN operations are executed more
from Intel Research Berkeley show that F Sort greatly out- swiftly when sorted data exist [15].
performs the traditional External Mergesort Algorithm both Sorting in WSDs can be performed in two modes, i) on-
in regards to time and energy consumption. We found sim- line: the data is continuously sorted upon the acquisition
ilar advantages in regards to the wearability constraints of of new measurements from the sensors, and ii) offline: the
flash media. data is stored on flash using some database scheme and is
periodically sorted upon request. A question that arises is
which of the two approaches delivers the best performance
1. INTRODUCTION on flash-based WSDs. Our experimental study presented in
The improvements in hardware design along with the wide Section 5 suggests that online sorting is two to three orders
availability of economically viable embedded sensor devices of magnitudes worse than offline sorting both for NAND and
make it feasible today to interact and understand the phys- NOR flash memory [14].
ical world at an extremely high fidelity [23, 21, 13]. Appli- The majority of WSDs utilize NAND-based flash memory
cations of Wireless Sensor Networks (WSNs) devices range for storing local measurements; we will further describe this
from environmental monitoring (such as atmosphere and specific type of flash memory in Section 2.1. NAND-based
habitant monitoring [23, 20, 3]) to seismic and structural [16] flash memory has some unique characteristics which need to
monitoring as well as industry manufacturing [6, 13]. be considered when designing data processing algorithms for
In many WSNs, recorded measurements are continuously it such as sorting. In Section 4 will address these constraints
transmitted to a base station for storage and analysis. How- when presenting the FSort algorithm.
ever, in long-term deployments it is often preferred to store
• Write-Constraint A: The minimum unit of write
operation in flash is a page. Page sizes vary between
256B to 4KB.
Permission to make digital or hard copies of all or part of this work for • Write-Constraint B: Pages on flash can only be
personal or classroom use is granted without fee provided that copies are written in sequential order, i.e., after page pi has been
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
written, any page pj , 1 ≤ j < i can not be written even
republish, to post on servers or to redistribute to lists, requires prior specific if it is empty.
permission and/or a fee.
DMSN ’09, August 24, 2009, Lyon, France • Erase-Constraint: A page pi cannot be deleted un-
Copyright c 2009 ACM 978-1-60558-777-6/09/08 ...$10.00. less the block that contains page pi has been erased.
 New record NAND-based flash memory installed on a WSD
Page Read Page Write Block Erase
Step 1. Find position k k 1.17mA 37mA 57mA
... Time 6.25ms 6.25ms 2.26ms
Energy 24µJ 763µJ 425µJ
Step 2. Read block records and erase Page Erase-Write Flash Idle Flash Sleep
... 43mA 0.068mA 0.031mA
Time 6.75ms N/A N/A
Step 3. Write records in sorted order Energy 957µJ 220µJ/sec 100µJ/sec
...

Step 4. Repeat Steps 1-3 with the excess record

Table 1: Performance Parameters for NAND-based
flash memory using a 3.3V voltage, 512B Page size
... and 16KB Block size
Block 1 Block 2 ... Block B
Our Contributions
Figure 1: Example of Online Sorting
In this paper we make the following contributions:
• We devise a sorting algorithm, coined FSort, which in-
• Wear-Constraint: The number of times a block can telligently exploits the characteristics of flash memory
be written or erased is limited (typically between 10,000 to deliver good performance both in terms of time and
to 100,000 times). energy;
• Fast Read/Slow Write-Constraint: Whereas typ- • We provide an extensive experimental evaluation us-
ically read and write access on a hard disk are almost ing traces from a real sensor network deployment at
identical, in flash it is much faster to read (≈60µs) Intel Research Berkeley [7] that shows the advantages
rather than to write (≈800µs). of offline over the online sorting and the superiority of
With the above characteristics/constraints of NAND-based FSort over existing algorithms.
flash memory in mind, we will examine which of the two sort-
The remainder of the paper is organized as follows: Sec-
ing approaches (online vs. offline) is superior by performing
tion 2 overviews the related research work and Section 3
some preliminary analysis. Let us consider the example de-
formalizes our system model and assumptions. Section 4
picted in Figure 1, which illustrates a flash memory consist-
introduces the FSort algorithm and its two phases. In Sec-
ing of B blocks each block containing P =4 pages. Also let
tion 5 we present our experimental study and finally Sec-
the flash memory contain N elements distributed through-
tion 6 concludes our paper.
out the blocks in sorted order (at some time τ ). Let us
assume that on time τ + 1 a new element arrives and needs
to be stored in sorted order. The first step is to discover 2. BACKGROUND AND RELATED WORK
the position k that the new element must be inserted (this
requires log(N ) reads assuming a binary search). When k is 2.1 Flash Memory
found, the block containing k is first read into memory (P Flash is a new generation of non-volatile memory that in-
reads) and then erased (due to the Erase-Constraint) such troduces many advantages compared to traditional storage
that it can be updated. If the block contains ≥1 empty media, including: shock-resistance, fast read access, low pro-
pages then the procedure finishes, otherwise the procedure duction cost and power efficiency. Flash memory is nowa-
continues to the next block with the excess page at hand. days the de-facto storage medium for WSDs and a variety
This technique is extremely inefficient to flash memory as it of other mobile devices.
consists of many write/erase operations that decrease both There are two types of flash memory, namely NOR and
the performance and lifetime of flash memory [5]. In fact, NAND [14] (both names are according to the internal struc-
we will demonstrate this level of detriment using a series of ture used in the respective media). NOR flash provides
microbenchmarks in Section 5. fast read access, slow write/erase time, low density and a
On the other hand, offline sorting requires the input to random-access interface. The latter property makes NOR
be sorted and written back to flash in a sequential manner flash ideal for application or boot code execution as it al-
only when requested. This is generally preferable in the lows direct access any address location. On the other hand,
case of flash memory as it has been shown that continuously NAND-flash has faster write/erase times and requires a smaller
executing random writes (as is the case of online sorting) chip area per cell; thus increasing the overall storage ca-
greatly degrades the performance (wearability, throughput) pacity; this also lowers the cost of NAND flash. However,
of flash media [5]. NAND flash does not allow random access to any memory
Our FSort algorithm extends the basic principles of offline location like NOR flash as it operates with a page-size in-
sorting to further enhance its performance by minimizing the terface.
write/erase operations. This provides efficient access to the
data stored on flash memory while increasing the longevity 2.2 Flash-based Databases
of the flash memory by spreading page writes out uniformly In this section we briefly describe some of the most pop-
so that the available storage capacity does not diminish at ular approaches to flash-based databases that try to cope
particular regions of the flash media. with the constraints mentioned in the Introduction.
 Symbol Definition
3,4 6,2 9,4 8,7 Input file N Flash capacity
Pass 0 M Available main memory (pages)
3,4 2,6 4,9 7,8 1-page runs B Number of Blocks in flash
bi Block with identifier i : 1 ≤ i ≤ B
Pass 1 P Number of Pages in a Block
2,3 4,7 pji Page with identifier i in block j
2-page runs
4,6 8,9
Pass 2 Table 2: Definition of Symbols
2,3
4,4 page the records contained are packed and appended sequen-
4-page runs
6,7 tially at the end of the flash, i.e., the next available empty
8,9 page. This scheme is highly beneficial as it eliminates fre-
quent small writes to flash media. Additionally this scheme
Pass 3 does not fragment flash memory as it operates in a top-down,
left-to-right manner (assuming a tabular representation of
Figure 2: External Sorting example with M =3 (2 the flash media), which satisfies the Write-Constraint B.
input and 1 output page buffers).
2.3 External Sorting
Sorting is one of the most fundamental problems in com-
• Flash Translation Layer (FTL): One way to de- puter science and has been extensively studied by the re-
ploy traditional hard disk-based database software on search community. External sorting arises when the num-
flash memory is by utilizing a Flash Translation Layer ber of records to be sorted is larger than the available main
(FTL) [12]. FTL maintains an internal mapping ta- memory of the system. The fundamentals of external sort-
ble between logical and physical pages that translates ing, including replacement selection and polyphase merging
write request to flash memory. This approach simpli- strategies have been thoroughly analyzed in [8] using tapes
fies the deployment of traditional database software as the storage medium. Since then, many works devised so-
but it also introduces a significant overhead on flash lutions to integrate and improve the performance of external
memory as most popular database systems require fre- sorting algorithms (I/O operations, memory requirements)
quent small log writes to store the old and updated on hard drives disks [18, 17, 9].
values of data. Traditional external sorting algorithms usually consist of
• Log Structured: The Log Structured approach (LSA) two phases: i) internal sorting, and ii) external merging.
[19] differs from FTL as it enables databases to access In the internal sorting phase, the input file (size S pages)
flash memory directly. LSA considers the database as is streamed into main memory, sorted on a page-to-page
one large log and any update to the database (i.e., log) basis and then written back to flash (Pass 0). The resulting
is appended at the end of flash memory. This approach sorted pages are called runs [8]. As soon as all runs are
uniformly distributes write requests on flash thus im- generated, the external merging phase starts. Assuming an
proving both performance and wearability. However, available memory of size M (pages), the external merging
like FTL, LSA suffers from the existence of frequent phase utilizes 1 page for output and M -1 pages for input
small log writes. Additionally, since only log pages buffers. On each subsequent pass, M -1 runs are fed into
are written on flash, when a database object (e.g., a the input buffers and are merged using the output buffer
record) is requested it has to be recreated by reading to produce longer runs. The output buffer is written out to
all associated log pages. flush and emptied so as to be used in the next pass. Figure 2
illustrates an example of external sorting with M =3 (2 input
• In-page Logging: A more recent approach, coined and 1 output page buffers).
In-page Logging (IPL) [11] tries to overcome the prob-
lems of LSA by storing the log records associated with 3. SYSTEM MODEL
a specific database page on the same block thus allow-
In this section we will formalize our basic terminology and
ing faster recreation of the database page. However,
assumptions. The main symbols and their respective defi-
frequent small writes also affect the IPL approach.
nitions are summarized in Table 2. For brevity in our de-
• AceDB flashlight: AceDB [10] attempts to overcome scriptions let us denote NAND-based flash memory as flash.
the small log frequent writes problem by maintaining Flash contains B blocks (b1 , b2 , ..., bB ) each containing P
a logical to physical page map in RAM. Additionally, pages. We define pji as page with identifier i : 1 ≤ i ≤ B
physical pages are allocated to logical pages on a trans- that belongs to block bj . We also assume that the WSD has a
action basis which allows for more sequential writes main memory module of capacity M (M pages). According
within a block. to our data model, each time a WSD acquires measurements
from the sensor-board it stores them sequentially on flash in
In this work, we assume that the data is structured on a top-down, left-to-right manner. In our experiments, we
flash media using a pack and append approach. In partic- assume that a measurement is acquired every 1ms.
ular, new records arising from continuous queries are main- At periodic time intervals τ1 , τ2 , ...(e.g., every 1024ms), a
tained in a buffer and when this buffer reaches the size of a user posts a query Q to the sensor network that requires
sorted data. Upon reception of Q, a sensor sorts the locally Algorithm 1 : FSort
stored data and transmits it over to its parent in the formed Input: D unsorted data pages, Available Flash Memory M ,
query routing tree. Note that the amount of data, X, sorted Buf :P = (M − 1) input buffers, min:1 output buffer
each time is linearly correlated with τi , i.e., τ1 = X, τ2 = Output: D sorted data pages
2X, τ3 = 3X, ... and so on. 1: procedure Sort
2: Allocate(Buf(P )); //Allocate P buffers for input
3: CountEmpty=0; //Terminating counter
4. THE FSORT ALGORITHM 4: //Initiate the Buf buffer array
In this section we describe our FSort algorithm. Similar to 5: for i = 1 to P do
the traditional external mergesort algorithm, FSort consists 6: set Bufi = p0i ;
of two phases, namely the internal sorting phase and the 7: end for
8: while true do
external merging phase which are described below: 9: //find the smallest key (min) and its index in Buf
10: set (min, BIndex) = SelectionTree(Buf );
1. Internal Sorting phase: During the internal sorting 11: Output(min); //write sorted output to flash
phase, M -1 buffers are created in available main mem- 12: //find the next page that the BufBInx must retrieve
ory that access blocks stored on flash in a sequential 13: set BufBIndex − > lastP ageRead+ = P ;
manner. Specifically, this phase produces sorted runs 14: set P Index = BufBIndex − > lastP ageRead;
by streaming data pages into memory, sorting them 15: //check if empty or new page
using a top-down replacement selection algorithm and 16: if (!IsEmptyOrNew(pBIndex
P Index ) then
outputting/appending them to the end of the flash me- 17: set BufBIndex = pBIndex
P Index ;
18: else
dia. 19: set CountEmpty + +;
2. External Merging phase: As soon as the sorted 20: end if
21: if (CountEmpty == P ) then
runs of the internal sorting phase are completed the 22: //all buffers read empty pages
external merging phase produces the sorted output 23: Break;
by merging the sorted runs recursively until a single 24: end if
sorted output is produced. 25: end while
26: Merge();
Our initial sorting phase algorithm accesses flash memory 27: end procedure
in a top-down manner by initiating a page buffer array in
available memory. Since in WSDs the amount of available
memory is very limited we have chosen to set the size of the (annotated as “Bufi − > lastP ageRead”) and assign it to a
buffer array equal to the number of pages in a block (usually temporary variable P Index while increasing it by 1 at the
8-16) [6, 4]. Data pages are continuously traversed until all same time (to access the next page) (line 13-14). If the page
input is examined. pointed by P Index is empty or if a sorted page has been
The intuition behind our approach is that the measure- outputted to this position (line 16) then we simply increase
ments generated by continuous queries in WSNs are not al- counter CountEmpty (line 19); this also removes the Buffer
tered erratically in small time windows. As a result, our ap- from the selection tree, otherwise we load the new page to
proach generates longer runs on each pass thus minimizing the current buffer (line 17). Finally, we test if there exists
the overall number of passes; decreasing in this way both more than one buffer accessing data pages and if not we exit
read, write and erase operations. Furthermore, accessing the loop (line 21-24). The procedure ends by recursively
pages in a top-down manner frees up empty space at the merging the runs (line 26).
top (as soon as all pages in a block have been fed to the As soon as the internal sorting phase begins, the sorted
buffer array the block can be erased). This is particularly runs are merged into longer runs by the external merging
useful as the erase of individual pages is not permitted in phase. This procedure continuous recursively and termi-
flash memory due to the Erase-Constraint mentioned in Sec- nates when a single sorted run is generated.
tion 1. Algorithm 1 outlines the operation of the internal
sorting phase of FSort.
Assuming that we have D unsorted data pages and an 5. EXPERIMENTS
available main memory M , our algorithm starts out by ini- In this section we present an experimental evaluation of
tiating a P -page buffer array, coined Buf , that will be used the FSort algorithm.
to traverse the flash memory in a top-down manner (line
2). We also set the counter CountEmpty to zero (line 5.1 Experimental Methodology
3); this counter will be used to halt the procedure when In order to evaluate the efficiency of our approach we de-
all buffers are accessing empty or new pages (i.e., we have veloped a flash-based simulator in C++. Our simulator sup-
read all data pages). The algorithm continues by stream- ports both NOR and NAND-based flash media settings and
ing the pages of the first block into the Buf array (lines the functions read and write. All experiments were per-
5-7). Next, the algorithm proceeds continuously by select- formed on a PC running Ubuntu Linux with 2GB of mem-
ing in each step the smallest key (or highest depending on ory and an Intel Core 2 Duo CPU running at 2.4GHz.
the request) including the buffer index, BIndex, that the
key was discovered (line 10) and forwards it to the output Power Model: We adopt the power model of the RISE
buffer (line 11). This is done efficiently by utilizing a se- platform [26] which consists of the following parameters:
lection tree. As soon as the key is outputted onto flash we We use a 14.8 MHz 8051 core operating at 3.3V with the
need to retrieve the next page for BufBindex . To do this, we following current consumption 14.8mA (On), 8.2mA (Idle),
store in the header of the buffer the current page position 0.2ţA (Off). We utilize a 128MB flash media with a page
size of 512B and a block size of 16KB. The current to read, Power (mJ) Read Write Erase
write and block delete was 1.17mA, 37mA and 57µA and the Online 47815 1519376 105789
time to read in the three pre-mentioned states was 6.25ms, NAND-flash Offline 96 3052 213
6.25ms, 2.27ms. Online 5998 189921 48279
NOR-flash Offline 96 3052 776
Datasets: We utilize a real trace of sensor readings that Time (s) Read Write Erase
is collected from 58 sensors deployed at the premises of Online 12452 12446 563
the Intel Research in Berkeley [7] between February 28th NAND-flash Offline 25 25 1
and April 5th, 2004. The sensors utilized in the deploy- Online 1562 1546 122
ment were equipped with weather boards and collected time- NOR-flash Offline 25 25 2
stamped topology information along with humidity, temper-
ature, light and voltage values once every 31 seconds (i.e.,
the epoch). The dataset includes 2.3 million readings col- Table 3: Performance comparison of the Online
lected from these sensors. (InsertionSort) and Offline (MergeSort) Sorting ap-
proaches
Algorithms: We first implement the External Insertion-
Sort and External MergeSort algorithms for comparing the
Energy Consumption Performance NAND-Flash
online vs. the offline sorting approaches on flash-based me-
160000
dia. We then implement the FSort algorithm and compare it MergeSort
against a version of the External MergeSort algorithm that 140000
FSort
utilizes M -1 buffer pages for input and one for output.

Energy Consumption (J)

120000
5.2 Experimental Results
100000
In this Section we present the results of our experimental
study. 80000

A. Online vs. Offline Sorting on Flash 60000

In our first experimental series we have conducted a micro
40000
benchmark that shows the deficiencies of online sorting on
flash memories used in WSDs. We have implemented: i) 20000
the InsertionSort algorithm, and ii) the External MergeSort
algorithm for benchmarking the online and offline sorting 0
1K 2K 4K 8K 16K 32K
approaches respectively. We feed 1000 records (1 record per
Data Pages
page) to our simulator and record the number of read, write
and erase operations which we then translate into time and
Figure 3: Energy Consumption performance com-
power consumption. Note, that we do not consider the en-
parison of External MergeSort and FSort for the
ergy required for executing the query as both approaches
light attribute. Sorting occurs every 1K records.
require the same energy for the given operation.
The results for both NOR and NAND-based flash mem-
ories are depicted on Table 3. We observe that the offline
We observe that FSort always maintains a competitive ad-
sorting approach greatly outperforms the online approach vantage over MergeSort for all data sizes (1-32K). The initial
on NAND and NOR-based flash memory both with regards
energy savings for 1K are ≈25% but as the number of records
to power and time. Specifically, we observe a decrease of
increases the energy savings also increase reaching as high as
power consumption and time by 3 orders of magnitudes on
≈41%. This is augmented to the fact that FSort minimizes
NAND-based flash memory and 2 orders of magnitudes on
write and erase operations by releasing continuous blocks of
NOR-based flash memory.
pages every time which are the most expensive operations;
this also increases the longevity of flash memory.
B. Power Consumption
In our second experimental series we measure the energy and
time performance of FSort and compare it with the exter- 6. CONCLUSIONS
nal Mergesort algorithm which the latter utilizes M -1 input In this paper we proposed a novel flash-aware and power-
buffers. We run experiments using three different attributes efficient algorithm coined FSort. FSort takes into account
included in our dataset, namely temperature, humidity and the limitations of WSNs as well as the characteristics / con-
light. The sensor records one attribute every 1ms and a straints of flash memory used in WSDs and improves both
query requests sorted results every 1024ms. Our simulator overall execution and response time performance.
executes both the external MergeSort and FSort algorithms Our experiments with real traces show that FSort, greatly
every 1024ms and collects energy and time statistics every outperforms the traditional external mergesort approach both
1024=1K records. Each experiment is executed 10 times with regards to time and energy performance (25-41% de-
and the average is collected. crease in overall energy consumption), by minimizing write
Figure 3 illustrates the results of our evaluation with re- and erase operations which are the most expensive oper-
gards to energy consumption1 for the light attribute; similar ations on flash. This also increases the longevity of flash
results apply to the humidity and temperature attributes.
correlated with energy consumption and do not present any
1
We omit the results of time performance as they are highly new findings.
memory as it only allows a limited number of write opera- 2007, ISBN:0-321-41506-X.
tions on each cell. [16] Ning X., Sumit R., Krishna K.C., Deepak G., Alan B.,
In the future we plan to extend our work by including Ramesh G., Deborah E., “A wireless sensor network For
index structures in order to access the data more efficiently structural monitoring”, In ACM SenSys, pp.13-24, 2004.
(i.e., minimize read operations). Additionally, we plan to [17] Nyberg C., Barclay T., Cvetanovic Z., Gray J., Lomet
assess the efficiency of our approach on other popular types D., “AlphaSort: a cache-sensitive parallel external sort”,
of flash memory like SSDs. In VLDB, Vol.4, No.4, pp.603-628, 1995.
[18] Pang H., Carey M.J., Livny M., “Memory-Adaptive
Acknowledgments External Sorting”, In VLDB, pp.618-629, 1993.
This work was supported in part by the Open University of [19] Rosenblum M., Ousterhout J.K., “The design and
Cyprus under the project SenseView, the US National Sci- implementation of a log-structured file system”, In
ence Foundation under the project AQSIOS (#IIS-0534531), ACM TOCS, Vol.10, No.1, pp.26-52, 1992.
the European Union under the project mPower (#034707) [20] Sadler C., Zhang P., Martonosi M., Lyon S.,
and IPAC (#224395), and the Cyprus national project GEI- “Hardware Design Experiences in ZebraNet”, In ACM
TONIA (#ΠΛYΠH/0506/31). SenSys, pp.227-238, 2004.
[21] Selavo L., Wood A., Cao Q., Sookoor T., Liu H.,
Srinivasan A., Wu Y., Kang W., Stankovic J., Yound
7. REFERENCES D., Porter J., “LUSTER: wireless sensor network for
environmental research”, In ACM SenSys, pp.103-116,
[1] Aly M., Chrysanthis P.k., Pruhs K., “Decomposing 2007.
Data-Centric Storage Query Hot-spots in Sensor
[22] Sharaf M.A. , Beaver J., Labrinidis A. and
Networks”, In MOBIQUITOUS, 2006.
Chrysanthis P.K., “TiNA: a scheme for temporal
[2] Aly M., Pruhs K., Chrysanthis P.k., “KDDCS: a coherency-aware in-network aggregation”, In MobiDe,
load-balanced in-network data-centric storage scheme pp.69-76, 2003.
for sensor networks”, In CIKM pp.317-326, 2006.
[23] Szewczyk R., Mainwaring A., Polastre J., Anderson J.,
[3] Andreou P., Zeinalipour-Yazti D., Vassiliadou M., Culler D., “An Analysis of a Large Scale Habitat
Chrysanthis P.K., Samaras G., ”KSpot: Effectively Monitoring Application”, In ACM SenSys, pp.214-226,
Monitoring the K Most Important Events in a Wireless 2004.
Sensor Network”, In ICDE, 2009.
[24] Yao Y., Gehrke J.E., ”The cougar approach to
[4] Atmel AT45DB041B, http://www.atmel.com/ in-network query processing in sensor networks”, In
[5] Bouganim L., Jonsson B.T., Bonnet P., SIGMOD Record, Vol.32, No.3, pp.9-18, 2002.
“uFLIP:Understanding Flash IO Patterns”, In CIDR,
[25] Zeinalipour-Yazti D., Andreou P., Chrysanthis P. and
2009. Samaras G., “MINT Views: Materialized In-Network
[6] Crossbow Technology Inc., http://www.xbow.com/ Top-k Views in Sensor Networks”, In IEEE MDM, 2007.
[7] Intel Lab Data [26] Zeinalipour-Yazti D., Lin S., Kalogeraki V.,
http://db.csail.mit.edu/labdata/labdata.html Gunopulos D., Najjar W., “MicroHash: An Efficient
[8] Knuth D.E., “The Art of Computer Programming: Index Structure for Flash-Based Sensor Devices”, In
Sorting and Searching” Addison Wesley, Vol. 3, April Usenix FAST, pp.31-44, 2005.
1997, ISBN:0-201-89685-0.
[9] Larson P., Graefe G., “Memory management during run
generation in external sorting”, In ACM SIGMOD,
pp.472-483, 1998.
[10] Lee K.Y., Kim H., Woo K., Chung Y.D., Kim M.H.,
“Design and implementation of MLC NAND
flash-based DBMS for mobile devices”, In Journal of
Systems and Software, 2009.
[11] Lee S., Moon B., “Design of Flash-Based DBMS: An
In-Page Logging Approach”, In ACM SIGMOD,
pp.1-10, 2007.
[12] Lee S., Park D., Chung T., Lee D., Park S., Song, H.,
“A log buffer-based flash translation layer using
fully-associative sector translation”, In ACM (TECS),
Vol.6, No.3, pp.18, 2007.
[13] Madden S.R., Franklin M.J., Hellerstein J.M., Hong
W., “TAG: a Tiny AGgregation Service for Ad-Hoc
Sensor Networks”, In USENIX OSDI, Vol.36,
pp.131-146, 2002.
[14] Masuoka F., Iizuka H., “Semiconductor memory device
and method for manufacturing the same ”, US
patent:4531203, July,1985.
[15] Elmasri R., Navathe S.B., “Fundamentals of Database
Systems (5th Edition):Chapter:15.3.2” Addison Wesley,