| |
-
Computing Optimal Subsets - Ronen Brafman, Ajay Mani, Shimony Eyal and Max Binshtok ; Submitted to American Association for Artificial Intelligence (AAAI), 2007 (submitted Jan 2007; send me an email for paper)
Various tasks in decision making and decision support require
selecting a preferred subset of items from a given set of feasible
items. Recent work in this area considered methods for
specifying such preferences based on the attribute values of
individual elements within the set. Of these, the approach
of (Brafman et al. 2006) appears to be the most general. In
this paper, we consider the problem of computing an optimal
subset given such a specification. The problem is shown to
be NP-hard in the general case, necessitating heuristic search
methods. We consider two algorithm classes for this problem:
direct set construction, and implicit enumeration as solutions
to appropriate CSPs. New algorithms are presented in each
class and compared empirically against previous results.
Heres the associated presentation on Computing Optimal Subsets
-
TINX – A Tiny Index Design for Flash Memory on Wireless Sensor Devices - Ajay Mani, Manjunath BR, Philip Levis; Oct 2006, In the proceedings of ACM Sensys, 2006 (Poster paper)
Flash memory is a cheap, viable storage alternative for
the low power, energy constrained sensor nodes. It is still
not clear however, what storage abstractions are best suited
to Sensornet applications.
The peculiar read, write and erase characteristics of flash
memory, imply that index data structures and other
storage management techniques developed for disks, which
often depend on in-place modification, may not be
appropriate for flash. This motivates us to explore
sophisticated data structures and algorithms that work around
the constraints and limitations of flash memory to provide an
efficient indexing mechanism.
We propose a new method of indexing data onto flash memory
that supports value-based range queries, time-based range
queries, hybrid queries
(combination of value-based and time-based range queries
with && and || operators) and aggregation queries (like
COUNT, MIN, MAX and AVERAGE). The indexing scheme
also maximizes wear-leveling, minimizes erases and
writes, minimizes RAM structures and maintains the index
and data on flash to facilitate easy block reclamation.
-
MStore: Enabling Storage-Centric Sensornet Research - Kresimir Mihic, Ajay Mani, Manjunath Rajashekhar, and Philip Levis; Submitted to Information Processing in Sensor Networks (IPSN), Sensor Platforms Tools and Design Methods, SPOTS, 2007 (submitted Nov. 2006)
We present MStore, an expansion board for telos and mica
family nodes that provides a non volatile memory hierarchy.
MStore has four memory chips: a 32KB FRAM, an 8MB
NOR flash, a 16MB NOR flash, and a 256MB NAND flash,
which can be expanded to 8GB if needed. All chips provide
an SPI bus interface to the node processor. MStore also
includes a Complex Programmable Logic Device (CPLD),
whose primary purpose is to be an SPI to parallel interface
for the NAND chip. The CPLD can also be used to offload
complex data processing.
Using TinyOS TEP-compliant drivers, we measure the
current draw and latencies of read, write, and erase operations
of different sizes on each of the storage chips. Through
this quantitative evaluation, we show that MStore’s manylevel
hierarchy and simple design provide an open and flexible
platform for sensor network storage research and experimentation.
-
Layered Virtual Binary Search Trees For Efficient Information Access in Self Organizing Decentralized P2P Networks - Ajay M, Manjunath BR; Nov 2004
In this paper we introduce layered
virtual binary tree structure, a scalable access
structure, specifically designed for Peer-
To-Peer information systems.
This tree structured ‘Grids’ are
constructed and maintained by using
algorithms based on local interactions, provide
reliable data access, and scale gracefully both
in storage and communication cost.
We provide a decentralized, scalable
information access structure and provide a
way to improve the highly chaotic and
inefficient Gnutella infrastructure with advanced
virtual tree topics.
We show a way to build a
binary tree network of peers, without having any
central authority or global knowledge. The grid
(network) construction takes place using largely
local interactions.
With the layered binary tree grid in
place, searches for information or resources
takes place with the minimum number of
messages sent into the network, thus having the
best utilization of the bandwidth.
|
|
|
