Andrey Balmin

Andrey Balmin

Auto-generated profile, based on publicly available information

Andrey Balmin

Platfora, Inc., USA

Research Focus & Metrics

Academic Career Length

27Years (2000-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
13 May 2004
Verified
Conference Paper
Closed access
VHV. Hristidis
V. Hristidis
YPY. Papakonstantinou
Y. Papakonstantinou
ABA. Balmin
A. Balmin
XKeyword provides efficient keyword proximity queries on large XML graph databases. A query is simply a list of keywords and does not require any schema or query language knowledge for its formulation. XKeyword is built on a relational database and, hence, can accommodate very large graphs. Query evaluation is optimized by using the graph's schema. In particular, XKeyword consists of two stages. In the preprocessing stage a set of keyword indices are built along with indexed path relations that describe particular patterns of paths in the graph. In the query processing stage plans are developed that use a near optimal set of path relations to efficiently locate the keyword query results. The results are presented graphically using the novel idea of interactive result graphs, which are populated on-demand according to the user's navigation and allow efficient information discovery. We provide theoretical and experimental points for the selection of the appropriate set of precomputed path relations. We also propose and experimentally evaluate algorithms to minimize the number of queries sent to the database to output the top-K results.

12 December 2004 in ACM Transactions on Database Systems
Verified
Journal Article
Open access
PDF file
ABAndrey Balmin
Andrey Balmin
YPYannis Papakonstantinou
Yannis Papakonstantinou
VVVictor Vianu
Victor Vianu
We investigate the incremental validation of XML documents with respect to DTDs, specialized DTDs, and XML Schemas, under updates consisting of element tag renamings, insertions, and deletions. DTDs are modeled as extended context-free grammars. "Specialized DTDs" allow the decoupling of element types from element tags. XML Schemas are abstracted as specialized DTDs with limitations on the type assignment. For DTDs and XML Schemas, we exhibit an O ( m log n ) incremental validation algorithm using an auxiliary structure of size O ( n ), where n is the size of the document and m the number of updates. The algorithm does not handle the incremental validation of XML Schema wrt renaming of internal nodes, which is handled by the specialized DTDs incremental validation algorithm. For specialized DTDs, we provide an O ( m log 2 n ) incremental algorithm, again using an auxiliary structure of size O ( n ). This is a significant improvement over brute-force re-validation from scratch.We exhibit a restricted class of DTDs called local that arise commonly in practice and for which incremental validation can be done in practically constant time by maintaining only a list of counters. We present implementations of both general incremental validation and local validation on an XML database built on top of a relational database.Our experimentation includes a study of the applicability of local validation in practice, results on the calibration of parameters of the auxiliary data structure, and results on the performance comparison between the general incremental validation technique, the local validation technique, and brute-force validation from scratch.

1 January 2010
Verified
Book Chapter
Open access
PDF file
JWJoel Wolf
Joel Wolf
DRDeepak Rajan
Deepak Rajan
KHKirsten Hildrum
Kirsten Hildrum
RKRohit Khandekar
Rohit Khandekar
VKVibhore Kumar
Vibhore Kumar
ABAndrey Balmin
Andrey Balmin
Originally, MapReduce implementations such as Hadoop employed First In First Out (fifo) scheduling, but such simple schemes cause job starvation. The Hadoop Fair Scheduler (hfs) is a slot-based MapReduce scheme designed to ensure a degree of fairness among the jobs, by guaranteeing each job at least some minimum number of allocated slots. Our prime contribution in this paper is a different, flexible scheduling allocation scheme, known as flex. Our goal is to optimize any of a variety of standard scheduling theory metrics (response time, stretch, makespan and Service Level Agreements (slas), among others) while ensuring the same minimum job slot guarantees as in hfs, and maximum job slot guarantees as well. The flex allocation scheduler can be regarded as an add-on module that works synergistically with hfs. We describe the mathematical basis for flex, and compare it with fifo and hfs in a variety of experiments.

24 February 2014
Verified
Conference Paper
Open access
PDF file
BBBin Bi
Bin Bi
YTYuanyuan Tian
Yuanyuan Tian
YSYannis Sismanis
Yannis Sismanis
ABAndrey Balmin
Andrey Balmin
JCJunghoo Cho
Junghoo Cho

27 March 2012
Verified
Conference Paper
Open access
PDF file
RVRares Vernica
Rares Vernica
ABAndrey Balmin
Andrey Balmin
KBKevin S. Beyer
Kevin S. Beyer
VEVuk Ercegovac
Vuk Ercegovac
We propose new adaptive runtime techniques for MapReduce that improve performance and simplify job tuning. We implement these techniques by breaking a key assumption of MapReduce that mappers run in isolation. Instead, our mappers communicate through a distributed meta-data store and are aware of the global state of the job. However, we still preserve the fault-tolerance, scalability, and programming API of MapReduce. We utilize these "situation-aware mappers" to develop a set of techniques that make MapReduce more dynamic: (a) Adaptive Mappers dynamically take multiple data partitions (splits) to amortize mapper start-up costs; (b) Adaptive Combiners improve local aggregation by maintaining a cache of partial aggregates for the frequent keys; (c) Adaptive Sampling and Partitioning sample the mapper outputs and use the obtained statistics to produce balanced partitions for the reducers. Our experimental evaluation shows that adaptive techniques provide up to 3x performance improvement, in some cases, and dramatically improve performance stability across the board.

18 June 2014
Verified
Conference Paper
Open access
PDF file
KKKonstantinos Karanasos
Konstantinos Karanasos
ABAndrey Balmin
Andrey Balmin
MKMarcel Kutsch
Marcel Kutsch
FOFatma Ozcan
Fatma Ozcan
VEVuk Ercegovac
Vuk Ercegovac
JJJesse Jackson
Jesse Jackson