문자의 빈도수를 고려한 Rank/Select 자료구조 구현 (pp.283-290)

권유진(Yoojin Kwon),이선호(Sunho Lee),박근수(Kunsoo Park) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.4

Rank/select 자료구조는 트리, 그래프, 문자열 인덱스 등의 다양한 자료구조를 간결하게 표현하는 기본 도구이다. Rank/select 자료구조는 주어진 문자열에 어느 위치까지 나타난 문자 개수를 세는 연산을 처리한다. 효율적인 rank/select 자료구조를 위해 이론적인 압축 방식들이 제안되었으나, 실제 구현에 있어 연산 시간 및 저장 공간의 효율을 보장할 수 없었다. 본 논문은 간단한 방법으로 이론적인 압축 크기를 보장하면서 연산 시간도 효율적인 rank/select 자료구조 구현 방법을 제시한다. 본 논문의 실험을 통해, 복잡한 인코딩 방법 없이도 이론적인 nH?+O(n) 비트 크기에 근접하면서 기존의 HSS 자료구조보다 빠른 rank/select 연산을 지원하는 구현 방법임을 보인다. The rank/select data structure is a basic tool of succinct representations for several data structures such as trees, graphs and text indexes. For a given string sequence, it is used to answer the occurrence of characters up to a certain position. In previous studies, theoretical rank/select data structures were proposed, but they didn’t support practical operational time and space. In this paper, we propose a simple solution for implementing rank/select data structures efficiently. According to experiments, our methods without complex encodings achieve nH?+O(n) bits of theoretical size and perform rank/select operations faster than the original HSS data structure.

2차원 비트행렬의 공간 효율적 Rank와 Select

김태성,나중채 한국정보과학회 2012 정보과학회논문지 : 시스템 및 이론 Vol.39 No.5

Succinct 표현은 n개의 이산 객체를 O(n) 비트만을 사용하여 저장하는 공간 효율적인 방법으로, 일반적으로 succinct 표현은 이산 객체에 접근하기 위해 비트 스트링에 대한 효율적인 rank와 select함수를 필요로 한다. 현재 다양한 연구들에 의해 1차원 비트 스트링의 rank와 select함수는 o(n) 비트의 보조 자료 공간을 사용하여 O(1) 시간에 수행되고, 실용적인 구현이 가능하다. 반면에, 2차원 비트 행렬에 대한 연구는 아직 초기단계이다. 본 논문에서는 2차원 비트 행렬 상에서의 rank 및 select 함수를 새롭게 정의하고 처음으로 o(n2) 비트만을 사용하여 O(logn) 시간에 rank 질의를, 그리고 O(log2n) 시간에 select 질의를 수행할 수 있는 방법을 제안한다.

Dynamic rank/select structures with applications to run-length encoded texts

Lee, S.,Park, K. North-Holland Pub. Co ; Elsevier Science Ltd 2009 Theoretical computer science Vol.410 No.43

Given an n-length text over a σ-size alphabet, we propose a framework for dynamic rank/select structures on the text and some of its applications. For a small alphabet with σ@?logn, we propose a two-level structure consisting of a counting scheme and a storing scheme that supports O(logn) worst-case time rank/select operations and O(logn) amortized time insert/delete operations. For a large alphabet with logn<σ@?n, we extend it to obtain O((1+logσloglogn)logn) worst-case time rank/select and O((1+logσloglogn)logn) amortized time insert/delete. Our structure provides a simple representation of an index for a collection of texts. In addition, we present rank/select structures on run-length encoding (RLE) of a text. For the n<SUP>'</SUP>-length RLE of an n-length text, our static version provides O(1) time select and O(loglogσ) time rank using n<SUP>'</SUP>logσ+O(n) bits and our dynamic version gives O((1+logσloglogn)logn) time operations in n<SUP>'</SUP>logσ+o(n<SUP>'</SUP>logσ)+O(n) bits.

조선시대 문과 중시 급제자 연구

원창애(Won ChangAe) 역사실학회 2009 역사와실학 Vol.39 No.-

Promotion Exam for Officials(PEO, in short, henceforth) were originally set up not for newly appointed persons, but for low officials of under Downward Low-Third Ranks(or Tang-ha-kwan). It was the 3rd king, Tae-jong, who looked for talented bureaucrats after he acceded to the throne in order to strengthen his administrative power. This was the background in which the PEO system was introduced for the first time. According to the formal regulation, PEO was regularly given once every ten years. The whole count, however, tells us that there were 57 times over all 479 years from the first conduct in 1407 A.D.(the 7th year of Tae-jong reign) to the last one in 1886 A.D.(the 23rd year of Ko-jong reign). The average term interval, then, was 8.4 years which fact implies that there were some additions which did not respect the rule; such a reign as king Se-jong, king Seong-jong, king Joong-jong, and king Young-jo. The most frequent conduct or the peak of the PEO was observed in 15th century and then it gradually declined. At last, there were less than half percent of the average number of passers for PEO, particularly, recorded around 19th century. This is a sharp contrast with other conducts, along with cannonical Civil Exams(or Moon-kwa), which had a various kind of Extraordinary Exams(or Pyeol-si). The more number of passers rapidly increased as Civil Exams went to the more later period in Joseon dynasty. The additional conduct of PEO shows at least two characteristics. In the first place, it was a king himself who was eager to tie closely with his supportive officials. This was a core reason of Selection-Exam-of-Gifted(or Pal-young-si) and Picking-up-Exam-of-Talented(or Teung-jun-si) which were originated in 1446 A.D., after the 7th king, Se-jo, conquered the opponents completely to be enthroned. The habitual conducts for PEO made it possible to be called Palace-Garden-Exam for Civil-Officials(or Moon-sin-jeong-si) comprehensively in "the Revised Version of Constitutive Law"(or Sok-tae-jon). This revision also allowed Upward-High-Third-Ranks(or Tang -sang-kwan) to take the exams too. For instance, the 21st king, Yoeng-jo, declared Picking-up-Exam-of-Talented in 1466 A.D. which Low-First-Ranks officials were, for the first time, permitted to take. Secondly, it was a good tool for a king to find loyal officials to get involved in a political renovation or revolution from time to time, in particular, such a reign as the 9th king, Seong-jong, and the 11th king Joong-jong. The former issued PEO twice even in a single period between 1477 and 1487 A.D., and the latter aimed a political reformation through Picking-up Exam. The analysis of former job careers for the whole passers in Joseon dynasty reveals that there were 7.3% of Upward -High-Third-Ranks(or Tang-sang-kwan), 65.7% of Low-Sixth -to-High-Third-Ranks(or Cham-sang-kwan), 17.3% of Down -ward-High-Seventh-Ranks(or Cham-ha-kwan), 7.1% of former officials(or Jeon-ham-kwan), and 2.6% of passers of Civil-Examinations and/or Temporary-Service-Members(or Keup-je and/or Kwon-ji). Among them, Low-Sixth -to-High-Third-Ranks(or Cham-sang-kwan) occupied the major portion. The detailed analysis on Low-Sixth-to-High-Third Ranks(or Cham-sang-kwan) includes a various members such as administrative practitioners in charge from E-joeng-pu, Six Ministries, and Each Subdivision Attached; Critical Inspectors from Hong-moon-kwan, Sa-kan-won, and Sa-heon-pu; teaching members from Seong-kyun-kwan, Se-ja-si -kang-won, and Jong-hak; former officials, military officials, and others. The 64.2% of Cham-sang-kwan were filled with officials of Fifth Rank and Sixth Rank. The half of this number, moreover, were from Six Ministries(or Yuk-jo) and Hong -moon-kwan. The highest position, Upward-High-Third-Ranks(or Tang-sang-kwan), was given to the PEO passers. Each category of the former positions shows a different ratio out of the same category to achieve the ultimate promotion; 71.4% of passers

Advancing feature ranking with hybrid feature ranking weighted majority model: a weighted majority voting strategy enhanced by the Harris hawks optimizer

Aljohani Mansourah,AbdulAzeem Yousry,Balaha Hossam Magdy,Badawy Mahmoud,Elhosseini Mostafa A 한국CDE학회 2024 Journal of computational design and engineering Vol.11 No.3

Feature selection (FS) is vital in improving the performance of machine learning (ML) algorithms. Despite its importance, identifying the most important features remains challenging, highlighting the need for advanced optimization techniques. In this study, we propose a novel hybrid feature ranking technique called the Hybrid Feature Ranking Weighted Majority Model (HFRWM2). HFRWM2 combines ML models with the Harris Hawks Optimizer (HHO) metaheuristic. HHO is known for its versatility in addressing various optimization challenges, thanks to its ability to handle continuous, discrete, and combinatorial optimization problems. It achieves a balance between exploration and exploitation by mimicking the cooperative hunting behavior of Harris’s hawks, thus thoroughly exploring the search space and converging toward optimal solutions. Our approach operates in two phases. First, an odd number of ML models, in conjunction with HHO, generate feature encodings along with performance metrics. These encodings are then weighted based on their metrics and vertically aggregated. This process produces feature rankings, facilitating the extraction of the top-K features. The motivation behind our research is 2-fold: to enhance the precision of ML algorithms through optimized FS and to improve the overall efficiency of predictive models. To evaluate the effectiveness of HFRWM2, we conducted rigorous tests on two datasets: “Australian” and “Fertility.” Our findings demonstrate the effectiveness of HFRWM2 in navigating the search space and identifying optimal solutions. We compared HFRWM2 with 12 other feature ranking techniques and found it to outperform them. This superiority was particularly evident in the graphical comparison of the “Australian” dataset, where HFRWM2 showed significant advancements in feature ranking.

Dynamic Compressed Representation of Texts with Rank/Select

Sunho Lee,Kunsoo Park 한국정보과학회 2009 Journal of Computing Science and Engineering Vol.3 No.1

Given an n-length text T over a σ-size alphabet, we present a compressed representation of T which supports retrieving queries of rank/select/access and updating queries of insert/delete. For a measure of compression, we use the empirical entropy H(T), which defines a lower bound nH(T) bits for any algorithm to compress T of n log σ bits. Our representation takes this entropy bound of T, i.e., nH(T) ≤ n log σ bits, and an additional bits less than the text size, i.e., o(n log σ) + O(n) bits. In compressed space of nH(T) + o(n log σ) + O(n) bits, our representation supports O(log n) time queries for a log n-size alphabet and its extension provides O((1+logσ/log log n) log n) time queries for a σ-size alphabet.

Site Specific Soil Fertility Ranking and Seasonal Paddy Variety Selection : An Intuitionistic Fuzzy Rough Set and Fuzzy Bayesian Based Decision Model

K. Lavanya,M. A. Saleem Durai,N. Ch. S. N. Iyengar 보안공학연구지원센터 2015 International Journal of Multimedia and Ubiquitous Vol.10 No.6

In decision making, crisp ranking is not possible when the entire attribute characteristics and their degree of importance are known precisely. In real world situations decision making takes place in an environment where the goals, the constraints, and the consequences of possible actions are not known precisely. Thus the best condition for classic decision making problem may not be satisfied when the situation involves both fuzzy and crisp data. Site specific soil fertility and seasonal crop selection data are characterized by high degree of fuzziness and uncertainty. In our model, intuitionistic fuzzy rough set establishes a close connection between the concepts of similarity and dissimilarity thereby providing an excellent framework for ranking soil fertility. Further fuzzy Bayesian incorporates both fuzzy and uncertainty in the probability model yielding more realistic seasonal paddy variety selection. The decision model introduced in this paper is suitable for both data rich and data poor environment. The results illustrate that the soil fertility ranking and successive paddy variety selection can help to sustain the soil fertility in subsequent rotations and minimize the loss of nutrients from the sites.

Improving classification accuracy of cancer types using parallel hybrid feature selection on microarray gene expression data

Lokeswari Venkataramana,Shomona Gracia Jacob,Rajavel Ramadoss,Dodda Saisuma,Dommaraju Haritha,Kunthipuram Manoja 한국유전학회 2019 Genes & Genomics Vol.41 No.11

Background Data mining techniques are used to mine unknown knowledge from huge data. Microarray gene expression (MGE) data plays a major role in predicting type of cancer. But as MGE data is huge in volume, applying traditional data mining approaches is time consuming. Hence parallel programming frameworks like Hadoop, Spark and Mahout are necessary to ease the task of computation. Objective Not all the gene expressions are necessary in prediction, it is very essential to select important genes for improving classification accuracy. So feature selection algorithms are parallelized and executed on Spark framework to eliminate unnecessary genes and identify only predictive genes in very less time without affecting prediction accuracy. Methods Parallelized hybrid feature selection (HFS) method is proposed to serve the purpose. This method includes parallelized correlation feature subset selection followed by rank-based feature selection methods. The selected subset of genes is evaluated using parallel classification algorithms. The accuracy values obtained are compared with existing rank-weight feature selection, parallelized recursive feature selection methods and also with the values obtained by executing parallelized HFS on DistributedWekaSpark. Results The classification accuracy obtained with the proposed parallelized HFS method is 97% and 79% for gastric cancer and childhood leukemia respectively. The proposed parallelized HFS method produced ~ 4% to ~ 15% improvement in classification accuracy when compared with previous methods. Conclusion The results reveal the fact that the proposed parallelized feature selection algorithm is scalable to growing medical data and predicts cancer sub-types in lesser time with higher accuracy.

Evaluating the Performance of Four Selections in Genetic Algorithms-Based Multispectral Pixel Clustering

Abdullah Al Rahat Kutubi,홍민기,김천 대한원격탐사학회 2018 大韓遠隔探査學會誌 Vol.34 No.1

This paper compares the four selections of performance used in the application of genetic algorithms (GAs) to automatically optimize multispectral pixel cluster for unsupervised classification from KOMPSAT-3 data, since the selection among three main types of operators including crossover and mutation is the driving force to determine the overall operations in the clustering GAs. Experimental results demonstrate that the tournament selection obtains a better performance than the other selections, especially for both the number of generation and the convergence rate. However, it is computationally more expensive than the elitism selection with the slowest convergence rate in the comparison, which has less probability of getting optimum cluster centers than the other selections. Both the ranked-based selection and the proportional roulette wheel selection show similar performance in the average Euclidean distance using the pixel clustering, even the ranked-based is computationally much more expensive than the proportional roulette. With respect to finding global optimum, the tournament selection has higher potential to reach the global optimum prior to the ranked-based selection which spends a lot of computational time in fitness smoothing. The tournament selection-based clustering GA is used to successfully classify the KOMPSAT-3 multispectral data achieving the sufficient thematic accuracy assessment (namely, the achieved Kappa coefficient value of 0.923).

Design of Space Search-Optimized Polynomial Neural Networks with the Aid of Ranking Selection and L2-norm Regularization

Dan Wang,Sung-Kwun Oh,Eun-Hu Kim 대한전기학회 2018 Journal of Electrical Engineering & Technology Vol.13 No.4

The conventional polynomial neural network (PNN) is a classical flexible neural structure and self-organizing network, however it is not free from the limitation of overfitting problem. In this study, we propose a space search-optimized polynomial neural network (ssPNN) structure to alleviate this problem. Ranking selection is realized by means of ranking selection-based performance index (RS_PI) which is combined with conventional performance index (PI) and coefficients based performance index (CPI) (viz. the sum of squared coefficient). Unlike the conventional PNN, L2-norm regularization method for estimating the polynomial coefficients is also used when designing the ssPNN. Furthermore, space search optimization (SSO) is exploited here to optimize the parameters of ssPNN (viz. the number of input variables, which variables will be selected as input variables, and the type of polynomial). Experimental results show that the proposed ranking selection-based polynomial neural network gives rise to better performance in comparison with the neuron fuzzy models reported in the literatures.