• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 135
Sort:
by name
by year
Article
С.Д. Кузнецов, Гомзин А. Г. Труды Института системного программирования РАН. 2015. Т. 27. № 4. С. 129-144.

he paper is devoted to methods for construction of socio-demographic profile of Internet users. Gender, age, political and religion views, region, relationship status are examples of demographic attributes. This work is a survey of methods that detect demographic attributes from user’s profile and messages. The most of surveyed works are devoted to gender detection. Age, political views and region are also interested researches. The most popular data sources for demographic attributes extraction are social networks, such as Facebook, Twitter, Youtube. The most of solutions are based on supervised machine learning. Machine learning allows to find target values (demographic attributes) dependencies from input data and use them to predict the value of the target attribute for the new data. The following problem solving steps are surveyed in the paper: feature extraction, feature selection, model training, evaluation. Researches use different kind of data to predict demographic attributes. The most popular data source is text. Words sequences (n-grams), parts of speech, emoticons, features specific to particular resources (eg, @ mentions and # Hashtags on Twitter) are extracted and used as input for machine learning algorithms. Social graphs are also used as source data. Communities of users that are automatically extracted from social graph are user as features for attributes prediction. Text data produces a lot of features. Feature selection algorithms are needed to reduce feature space. The paper surveys feature selection, classification and regression algorithms, evaluation metrics.

Added: Jan 23, 2018
Article
Твардовский A., Евтушенко Н. В., Громов М. Труды Института системного программирования РАН. 2017. Т. 29. № 4. С. 139-154.
Added: Nov 9, 2017
Article
Захаров В. А. Труды Института системного программирования РАН. 2015. Т. 27. № 2. С. 221-250.

Finite state transducers extend the finite state automata to model functions on strings or lists. They may be used also as simple models of sequential reactive programs. These programs operate in the interaction with the environment permanently receiving data (requests) from it. At receiving a piece of data such program performs a sequence of actions. When certain control points are achieved a program outputs the current results of computation as a response. It is significant that different sequences of actions may yield the same result. Therefore, the basic actions of a program may be viewed as generating elements of some appropriate semigroup, and the result of computation may be regarded as the composition of actions performed by the program. This paper offers an alternative technique for the analysis of finite state transducers over semigroups. To check the equivalence of two initial transducers we associate with them a Labeled Transition Systems (LTS). Each path in this LTS represents all possible runs of the initial transducers on the same input word. Every node of the LTS keeps track of the states of the initial transducers achieved at reading some input word and the deficiency of the output words computed so far. If both transducers reach their final states and the deficiency of their outputs is nonzero then this indicates that the initial transducers produce different images for the same word, and, hence, they are not equivalent. The nodes of the LTS that capture this effect are called rejecting nodes. Thus, the equivalence checking of the initial transducers is reduced to checking the reachability of rejecting nodes in the LTS. We show that one needs to analyze only a bounded fragment of the LTS to certify (un)reachability of rejecting nodes. The size of this fragment is polynomial of the size of the initial transducers if both transducers are deterministic, and single-exponential if they are k-bounded. The same approach is applicable for checking k-valuedness of transducers over semigroups.

Added: Sep 30, 2015
Article
Зеленов С. В., Зеленова С. Труды Института системного программирования РАН. 2017. Т. 29. № 5. С. 257-282.
Added: Feb 12, 2018
Article
Гетьман А. И., Маркин Ю. В., Иванников В. П. и др. Труды Института системного программирования РАН. 2015. Т. 27. № 4. С. 5-22.
Added: Sep 5, 2019
Article
Гетьман А. И., Маркин Ю. В., Обыденков Д. О. и др. Труды Института системного программирования РАН. 2017. Т. 29. № 3. С. 117-150.
Added: Sep 5, 2019
Article
Татарников А. Д. Труды Института системного программирования РАН. 2017. Т. 29. № 1. С. 167-194.
Added: Nov 8, 2017
Article
Мендкович Н. А., Кузнецов С. Д. Труды Института системного программирования РАН. 2012. Т. 23. С. 195-214.

The presented overview is concerned with lexical query optimization and covers papers published in the last four decades. The paper consists of five sections. The first section – Introduction – classifies query optimization techniques into semantic optimizations and lexical optimizations. Semantic optimizations usually relies on data integrity rules that are stores within metadata part of databases, and on data statistics. This kind of optimizations is discussed in many textbooks and papers. Lexical optimizations (more often called rewriting) use only a text of query and no other information about database and its structure. Lexical optimizations are further classified into query transformations, query amelioration, and query reduction. The second section of the paper discusses techniques of query transformation such as predicate pushdown, transformation of nested query into query with joins, etc. Query amelioration is a topic of the third section with a focus on magic set optimizations. The forth section covers query reduction optimizations. The section briefly describes traditional approaches (such as tableau-based) and considers in more details three new algorithms proposed by authors. The fifth section concludes the paper.

Added: Nov 1, 2017
Article
Казаков К., Семенов В. А. Труды Института системного программирования РАН. 2016. Т. 28. № 4. С. 241-294.
Added: Dec 12, 2018
Article
Петренко А. К., Кулямин В. В., Хорошилов А. В. Труды Института системного программирования РАН. 2015. Т. 27. № 5. С. 175-190.
Added: Aug 28, 2017
Article
Казаков К., Семенов В. А. Труды Института системного программирования РАН. 2017. Т. 29. № 5. С. 185-238.
Added: Dec 12, 2018
Article
Аничкин А., Семенов В. А. Труды Института системного программирования РАН. 2017. Т. 29. № 3. С. 247-296.
Added: Dec 12, 2018
Article
С.Д. Кузнецов Труды Института системного программирования РАН. 2015. Т. 27. № 1. С. 173-192.

In 2005, I wrote an article in which I discussed the most important features of the standards ODMG 3.0 (ODMG object model) and the SQL:2003 (SQL data model) and convincingly (as it seemed to me) argued that the similarity between the object model and object extensions to SQL is purely external, that close in mind syntactic constructions hide deep differences at the model level. Since then, it took many years for which I understood many things that were wrongly or insufficient correctly understood by me then, and gradually came to the conclusions that: 1.    differences that seemed to me deep, are not such, and indeed are not differences at the model level; 2.    the object extensions of SQL provide no less (and rather large) capabilities than the ODMG object model; 3.    reasonably (from the standpoint of the database community) used DBMSes based on the ODMG data model, one will create databases and tools to manipulate them similar to those prescribed by the SQL data model.

Added: Jan 23, 2018
Article
Захаров В. А., Абрамова И. В., Варновский Н. П. и др. Труды Института системного программирования РАН. 2019. Т. 31. № 6. С. 145-162.

 In this paper, we study the possibility of using a certain cloud computing model supplied with cryptoservers to obfuscate software programs. Earlier, we proposed this cloud computing model in our study of some information security problems for multi-client distributed computing over encrypted data. Based on this model, we proposed a new approach involving the use of threshold homomorphic cryptosystems for program obfuscation. The main result of this paper is a new definition of the resistance of obfuscation of programs in the cloud computing model and a theorem proving the cryptographic strength of the proposed algorithm of obfuscation of programs under the assumption of the existence of cryptographically strong threshold homomorphic encryption systems. The paper is organized as follows. In the introducing section we discuss the main aspects of the information security problems for cloud computing systems. Section 2 provides a description of the obfuscation program objectives, as well as a brief overview of the main achievements in its study. The next section provides general information about homomorphic cryptosystems. Section 4 describes a more special class of homomorphic cryptosystems - threshold homomorphic encryption systems. Section 5 introduces the cloud computing model, which is used as framework for our program obfuscation techniques. For this computing environment, in Section 6, the definition of the cryptographic strength of program obfuscation is formulated, a new method of program obfuscation using threshold homomorphic cryptosystems is described, and the cryptographic strength of the proposed obfuscation algorithm is proved. 

Added: Feb 19, 2020
Article
Дворянский Л. В. Труды Института системного программирования РАН. 2011. № 20. С. 71-94.
Added: Sep 20, 2012
Article
Кудряшов Е. А., Мельник Д. М., Монаков А. В. Труды Института системного программирования РАН. 2016. Т. 28. № 1. С. 63-80.

The paper discusses an optimization approach for external calls in positionindependent code that is based on loading the callee address immediately at the call site from the Global Offset Table (GOT), avoiding the use of the Procedure Linkage Table (PLT). Normally the Linux toolchain creates the PLT both in the main executable (which comprises position-dependent code and has to rely on the PLT mechanism to make external calls) and in shared libraries, where the PLT serves to implement lazy binding of dynamic symbols, but is not required otherwise. However, calls via the PLT have some overhead due to an extra jump instruction and poorer instruction cache locality. On some architectures, binary interface of PLT calls constrains compiler optimization at the call site. It is possible to avoid the overhead of PLT calls by loading the callee address from the GOT at the call site and performing an indirect call, although it prevents lazy symbol resolution and may cause increase in code size. We implement this code generation variant in GCC compiler for x86 and ARM architectures. On ARM, loading the callee address from the GOT at call site normally needs a complex sequence with three load instructions. To improve that, we propose new relocation types that allow to build a PC-relative address of a given GOT slot with a pair of movt, movw instructions, and implement these relocation types in GCC and Binutils (assembler and linker) for both ARM and Thumb-2 modes. Our evaluation results show that proposed optimization yields performance improvements on both x86 (up to 12% improvement with Clang/LLVM built with multiple shared libraries, on big translation units) and ARM (up to 7% improvement with SQLite, average over several tests), even though code size on ARM also grows by 13-15%.

Added: Nov 5, 2018
Article
Аветисян А. И., Мельник Д., Курмангалеев Ш. Ф. и др. Труды Института системного программирования РАН. 2014. Т. 26. № 1. С. 343-356.

The paper describes the workflow for optimizing programs for performance targeting the fixed hardware architecture with static compilation using GCC and LLVM compilers as examples. The workflow has gradually grown within ISP RAS Compiler Technology Team when working on GCC and LLVM compiler optimization. We start with preparing a benchmark using the given application as a source, and then proceed in parallel with manual analysis of generated assembly code and automatic compiler tuning tool. In general, a compiler optimization improvement produced by the manual analysis gives 1-5% speedup, while the automatic tuning results may give up to 10-20% speedup. However, the manual analysis results are usually valid for the broad class of applications and are contributed to the open source compilers, while the automatic tuning results make sense only for the given application. We present some of the optimizations performed, e.g. improved NEON and Thumb-2 support for GCC, vectorization improvements for LLVM, register allocation improvements for LLVM, and the corresponding evaluation results. We also describe TACT, a tool for automatic compiler tuning for the given application mentioned above, and its example use cases both for an application developer and a compiler engineer. We give the sample of TACT optimization results.

Added: Mar 22, 2017
Article
Емеленко А., Маллачиев К., Пакулин Н. В. Труды Института системного программирования РАН. 2017. Т. 29. № 4. С. 295-302.
Added: Feb 12, 2018
Article
С.Д. Кузнецов, Мендкович Н. А. Труды Института системного программирования РАН. 2013. Т. 25. С. 113-130.

This paper describes enhanced algorisms of lexical optimization query. These algorisms detect and remove redundant conditions from query restriction to simplify it. The paper also presents results of implementation of these optimization techniques and those effects on query processing speed. The paper includes four sections. The first section (Introduction) provides general context of the paper. The second section describes three proposed algorithms of lexical query optimization. The first one is the algorithm of absorption. This algorithm allows to find and remove a wide set of conditions that are redundant but are not equal textually even after standardization of whole restriction expression. The second algorithm is an adaptation of well-known Quin-McCluskey algorithm initially designed for minimization of Boolean functions. The last algorithm of lexical query optimization is based on techniques for optimization of systems of linear inequalities. The third section of the paper discusses results of efficiency evaluation of the proposed algorithms. The forth section concludes the paper.

Added: Nov 6, 2017
Article
С.Д, Кузнецов, Мендкович Н. А. Труды Института системного программирования РАН. 2013. Т. 25. С. 113-130.

This paper describes enhanced algorisms of lexical optimization query. These algorisms detect and remove redundant conditions from query restriction to simplify it. The paper also presents results of implementation of these optimization techniques and those effects on query processing speed. The paper includes four sections. The first section (Introduction) provides general context of the paper. The second section describes three proposed algorithms of lexical query optimization. The first one is the algorithm of absorption. This algorithm allows to find and remove a wide set of conditions that are redundant but are not equal textually even after standardization of whole restriction expression. The second algorithm is an adaptation of well-known Quin-McCluskey algorithm initially designed for minimization of Boolean functions. The last algorithm of lexical query optimization is based on techniques for optimization of systems of linear inequalities. The third section of the paper discusses results of efficiency evaluation of the proposed algorithms. The forth section concludes the paper.

Added: Jan 30, 2018
Article
Дробышевский М., Коршунов А., Turdakov D. Y. Proceedings of the Institute for System Programming of the RAS. 2016. Vol. 28. No. 6. P. 153-170.
Added: Aug 28, 2017