college+of+engineering
-
Biomimetic Resonant Acoustic Sensor Detecting Far-Distant Voices Accurately to Hit the Market
A KAIST research team led by Professor Keon Jae Lee from the Department of Materials Science and Engineering has developed a bioinspired flexible piezoelectric acoustic sensor with multi-resonant ultrathin piezoelectric membrane mimicking the basilar membrane of the human cochlea. The flexible acoustic sensor has been miniaturized for embedding into smartphones and the first commercial prototype is ready for accurate and far-distant voice detection.
In 2018, Professor Lee presented the first concept of a flexible piezoelectric acoustic sensor, inspired by the fact that humans can accurately detect far-distant voices using a multi-resonant trapezoidal membrane with 20,000 hair cells. However, previous acoustic sensors could not be integrated into commercial products like smartphones and AI speakers due to their large device size.
In this work, the research team fabricated a mobile-sized acoustic sensor by adopting ultrathin piezoelectric membranes with high sensitivity. Simulation studies proved that the ultrathin polymer underneath inorganic piezoelectric thin film can broaden the resonant bandwidth to cover the entire voice frequency range using seven channels. Based on this theory, the research team successfully demonstrated the miniaturized acoustic sensor mounted in commercial smartphones and AI speakers for machine learning-based biometric authentication and voice processing. (Please refer to the explanatory movie KAIST Flexible Piezoelectric Mobile Acoustic Sensor).
The resonant mobile acoustic sensor has superior sensitivity and multi-channel signals compared to conventional condenser microphones with a single channel, and it has shown highly accurate and far-distant speaker identification with a small amount of voice training data. The error rate of speaker identification was significantly reduced by 56% (with 150 training datasets) and 75% (with 2,800 training datasets) compared to that of a MEMS condenser device.
Professor Lee said, “Recently, Google has been targeting the ‘Wolverine Project’ on far-distant voice separation from multi-users for next-generation AI user interfaces. I expect that our multi-channel resonant acoustic sensor with abundant voice information is the best fit for this application. Currently, the mass production process is on the verge of completion, so we hope that this will be used in our daily lives very soon.”
Professor Lee also established a startup company called Fronics Inc., located both in Korea and U.S. (branch office) to commercialize this flexible acoustic sensor and is seeking collaborations with global AI companies.
These research results entitled “Biomimetic and Flexible Piezoelectric Mobile Acoustic Sensors with Multi-Resonant Ultrathin Structures for Machine Learning Biometrics” were published in Science Advances in 2021 (7, eabe5683).
-Publication
“Biomimetic and flexible piezoelectric mobile acoustic sensors with multiresonant ultrathin structures for machine learning biometrics,” Science Advances (DOI: 10.1126/sciadv.abe5683)
-Profile
Professor Keon Jae Lee
Department of Materials Science and Engineering
Flexible and Nanobio Device Lab
http://fand.kaist.ac.kr/
KAIST
2021.06.14 View 5419 -
Krafton Matches Alumni Donations to Raise 11 Billion KRW for SW Developers
Alumni donations from the School of Computing, including Baemin and Devsisters, continue to grow
Alumni from the KAIST School of Computing who are current and former developers at the leading game company Krafton, established by KAIST alumna Byung-Gyu Chang, made an agreement to help raise 11 billion KRW during a ceremony on June 4. The funds raised in the matching grant will be used to nurture software developers.
Krafton Chairman Chang donated 10 billion won last January. His donation inspired other alumni working at Krafton as well as its former developers. Eleven KAIST alumni raised 5.5 billion KRW in two months and discussed the matching grant idea with Chairman Chang.
The Krafton matching grant ceremony was attended by President Kwang Hyung Lee, Provost and Executive Vice President Seung Seob Lee, Vice President for Research Sang Yup Lee, Head of the School of Computing Sukyoung Ryu, Krafton Chairman Byung-gyu Chang, and KAIST alumnus from Krafton Seung-woo Shin. Other alumni donors including Krafton CEO Changhan Kim joined the ceremony online.
Krafton CEO Changhan Kim said, “Just as our alma mater played an important role in growing our company, we hope that our donation could help support good developers. This will not only help our company, but advance our industry.”
KAIST and Krafton also signed a business agreement to foster competitive developers. Krafton said it plans to continue giving back to society through the matching grant program.
Head of the School of Computing Sukyoung Ryu thanked Chairman Chang and alumni who took part in the fund raising, saying, “To take the lead in rapidly changing computer technology, we desperately need more top students, faculty members, and facilities. We need more resources and infrastructure for interdisciplinary research.”
The School of Computing has seen significant growth recently. Its number of undergraduate students has increased from 450 in 2016 to more than 900 in 2021. With this donation, the school will expand its current buildings to provide diverse educational and mentoring programs in more spacious facilities.
Seung-woo Shin (Class of ’92), who joined Krafton’s matching grant, said, “I have always been thankful for the people I met and what I learned at KAIST. I was moved by the idea of giving back to the school.”
Seong-jung Ryu (Class of ’97) said, “This donation reminded me of the good times I had back then. I thought it was crucial that the department’s facilities be extended, so I naturally wanted to take part.”
Alumni donations, especially from the School of Computing, have also continued to grow more recently. Woowa Brothers Corp. CEO Beom-Jun Kim, the developer of the meal delivery app ‘Baemin’ donated 100 million KRW in April. Baemin became the most used app in the country during the COVID-19 pandemic.
He explained, “I have been thinking about ways to give something to the next generation, rather than ‘paying back’ those who helped me in the past.”
Encouraged by Baemin’s donation, alumni couple Ha-Yeon Seo and Dong-Hun Hahn from the School of Computing and eleven alumni engineers working at Devsisters Corp. also followed suit.
2021.06.09 View 4833 -
Natural Rainbow Colorants Microbially Produced
Integrated strategies of systems metabolic engineering and membrane engineering led to the production of natural rainbow colorants comprising seven natural colorants from bacteria for the first time
A research group at KAIST has engineered bacterial strains capable of producing three carotenoids and four violacein derivatives, completing the seven colors in the rainbow spectrum. The research team integrated systems metabolic engineering and membrane engineering strategies for the production of seven natural rainbow colorants in engineered Escherichia coli strains. The strategies will be also useful for the efficient production of other industrially important natural products used in the food, pharmaceutical, and cosmetic industries.
Colorants are widely used in our lives and are directly related to human health when we eat food additives and wear cosmetics. However, most of these colorants are made from petroleum, causing unexpected side effects and health problems. Furthermore, they raise environmental concerns such as water pollution from dyeing fabric in the textiles industry. For these reasons, the demand for the production of natural colorants using microorganisms has increased, but could not be readily realized due to the high cost and low yield of the bioprocesses.
These challenges inspired the metabolic engineers at KAIST including researchers Dr. Dongsoo Yang and Dr. Seon Young Park, and Distinguished Professor Sang Yup Lee from the Department of Chemical and Biomolecular Engineering. The team reported the study entitled “Production of rainbow colorants by metabolically engineered Escherichia coli” in Advanced Science online on May 5. It was selected as the journal cover of the July 7 issue.
This research reports for the first time the production of rainbow colorants comprising three carotenoids and four violacein derivatives from glucose or glycerol via systems metabolic engineering and membrane engineering. The research group focused on the production of hydrophobic natural colorants useful for lipophilic food and dyeing garments. First, using systems metabolic engineering, which is an integrated technology to engineer the metabolism of a microorganism, three carotenoids comprising astaxanthin (red), -carotene (orange), and zeaxanthin (yellow), and four violacein derivatives comprising proviolacein (green), prodeoxyviolacein (blue), violacein (navy), and deoxyviolacein (purple) could be produced. Thus, the production of natural colorants covering the complete rainbow spectrum was achieved.
When hydrophobic colorants are produced from microorganisms, the colorants are accumulated inside the cell. As the accumulation capacity is limited, the hydrophobic colorants could not be produced with concentrations higher than the limit. In this regard, the researchers engineered the cell morphology and generated inner-membrane vesicles (spherical membranous structures) to increase the intracellular capacity for accumulating the natural colorants. To further promote production, the researchers generated outer-membrane vesicles to secrete the natural colorants, thus succeeding in efficiently producing all of seven rainbow colorants. It was even more impressive that the production of natural green and navy colorants was achieved for the first time.
“The production of the seven natural rainbow colorants that can replace the current petroleum-based synthetic colorants was achieved for the first time,” said Dr. Dongsoo Yang. He explained that another important point of the research is that integrated metabolic engineering strategies developed from this study can be generally applicable for the efficient production of other natural products useful as pharmaceuticals or nutraceuticals. “As maintaining good health in an aging society is becoming increasingly important, we expect that the technology and strategies developed here will play pivotal roles in producing other valuable natural products of medical or nutritional importance,” explained Distinguished Professor Lee.
This work was supported by the "Cooperative Research Program for Agriculture Science & Technology Development (Project No. PJ01550602)" Rural Development Administration, Republic of Korea.
-Publication:Dongsoo Yang, Seon Young Park, and Sang Yup Lee. Production of rainbow colorants by metabolically engineered Escherichia coli. Advanced Science, 2100743.
-Profile Distinguished Professor Sang Yup LeeMetabolic &Biomolecular Engineering National Research Laboratoryhttp://mbel.kaist.ac.kr
Department of Chemical and Biomolecular EngineeringKAIST
2021.06.09 View 5239 -
Ultrafast, on-Chip PCR Could Speed Up Diagnoses during Pandemics
A rapid point-of-care diagnostic plasmofluidic chip can deliver result in only 8 minutes
Reverse transcription-polymerase chain reaction (RT-PCR) has been the gold standard for diagnosis during the COVID-19 pandemic. However, the PCR portion of the test requires bulky, expensive machines and takes about an hour to complete, making it difficult to quickly diagnose someone at a testing site. Now, researchers at KAIST have developed a plasmofluidic chip that can perform PCR in only about 8 minutes, which could speed up diagnoses during current and future pandemics.
The rapid diagnosis of COVID-19 and other highly contagious viral diseases is important for timely medical care, quarantining and contact tracing. Currently, RT-PCR uses enzymes to reverse transcribe tiny amounts of viral RNA to DNA, and then amplifies the DNA so that it can be detected by a fluorescent probe. It is the most sensitive and reliable diagnostic method.
But because the PCR portion of the test requires 30-40 cycles of heating and cooling in special machines, it takes about an hour to perform, and samples must typically be sent away to a lab, meaning that a patient usually has to wait a day or two to receive their diagnosis.
Professor Ki-Hun Jeong at the Department of Bio and Brain Engineering and his colleagues wanted to develop a plasmofluidic PCR chip that could quickly heat and cool miniscule volumes of liquids, allowing accurate point-of-care diagnoses in a fraction of the time. The research was reported in ACS Nano on May 19.
The researchers devised a postage stamp-sized polydimethylsiloxane chip with a microchamber array for the PCR reactions. When a drop of a sample is added to the chip, a vacuum pulls the liquid into the microchambers, which are positioned above glass nanopillars with gold nanoislands. Any microbubbles, which could interfere with the PCR reaction, diffuse out through an air-permeable wall. When a white LED is turned on beneath the chip, the gold nanoislands on the nanopillars quickly convert light to heat, and then rapidly cool when the light is switched off.
The researchers tested the device on a piece of DNA containing a SARS-CoV-2 gene, accomplishing 40 heating and cooling cycles and fluorescence detection in only 5 minutes, with an additional 3 minutes for sample loading. The amplification efficiency was 91%, whereas a comparable conventional PCR process has an efficiency of 98%. With the reverse transcriptase step added prior to sample loading, the entire testing time with the new method could take 10-13 minutes, as opposed to about an hour for typical RT-PCR testing. The new device could provide many opportunities for rapid point-of-care diagnostics during a pandemic, the researchers say.
-Publication
Ultrafast and Real-Time Nanoplasmonic On-Chip Polymerase Chain Reaction for Rapid and Quantitative Molecular Diagnostics
ACS Nano (https://doi.org/10.1021/acsnano.1c02154)
-Professor
Ki-Hun Jeong
Biophotonics Laboratory
https://biophotonics.kaist.ac.kr/
Department of Bio and Brain Engineeinrg
KAIST
2021.06.08 View 4924 -
KAIST to join Deep Space Exploration Project
KAIST agreed to launch the Deep Space Exploration Research Consortium with two key leading aerospace research institutes, the Korea Aerospace Research Institute (KARI) and the Korea Astronomy and Space Science Institute (KASI) during a recent meeting at the KAIST campus. President Kwang Hyung Lee, KARI President Sang-Yool Lee, KASI President Young-Deuk Park, and Vice Minister of Science and ICT Hong-taek Yong attended the meeting to discuss medium- and long-term deep space exploration plans and collaborations.
The three entities have cooperated in scientific research for the last 30 years during which Korea has been developing its space exploration expertise. They signed the MoU for Cooperation for R&D and Industrialization on Deep Space Exploration’ last December. The research consortium will share and discuss research plans for space science research and exploration technology, and contribute to planning the nation’s deep space exploration.
At the meeting, KAIST reported its plans to return KITSAT-1 to Earth, Korea’s first satellite using local technology, and to explore the radiation belt (the Van Allen belt) around Earth. KAIST launched Korea’s first satellite KITSAT-1 in 1992. Meanwhile, KARI shared their plans to launch a lunar landing module using a Korean Space Launch Vehicle by 2030 and explained the current technologies and research related to a lunar landing and space exploration. Based on the payload technology it has been building on for the last 20 years, KASI emphasized the importance of research for deep space exploration in relation to the formation of the universe and the origin of mankind.
Vice Minister of Science and Technology Yong also stressed that “to enhance Korea’s capabilities for space research after launching our space launch vehicle, Nuri, in October, there must be continued efforts and preparation for higher level space research, including space exploration planning. The various experts’ opinions discussed in today’s meeting will be taken into consideration for governmental policies related to the ‘National Space Exploration Roadmap’ to be established in the latter half of this year.”
2021.06.07 View 3914 -
What Guides Habitual Seeking Behavior Explained
A new role of the ventral striatum explains habitual seeking behavior
Researchers have been investigating how the brain controls habitual seeking behaviors such as addiction. A recent study by Professor Sue-Hyun Lee from the Department of Bio and Brain Engineering revealed that a long-term value memory maintained in the ventral striatum in the brain is a neural basis of our habitual seeking behavior. This research was conducted in collaboration with the research team lead by Professor Hyoung F. Kim from Seoul National University. Given that addictive behavior is deemed a habitual one, this research provides new insights for developing therapeutic interventions for addiction.
Habitual seeking behavior involves strong stimulus responses, mostly rapid and automatic ones. The ventral striatum in the brain has been thought to be important for value learning and addictive behaviors. However, it was unclear if the ventral striatum processes and retains long-term memories that guide habitual seeking.
Professor Lee’s team reported a new role of the human ventral striatum where long-term memory of high-valued objects are retained as a single representation and may be used to evaluate visual stimuli automatically to guide habitual behavior.
“Our findings propose a role of the ventral striatum as a director that guides habitual behavior with the script of value information written in the past,” said Professor Lee.
The research team investigated whether learned values were retained in the ventral striatum while the subjects passively viewed previously learned objects in the absence of any immediate outcome. Neural responses in the ventral striatum during the incidental perception of learned objects were examined using fMRI and single-unit recording.
The study found significant value discrimination responses in the ventral striatum after learning and a retention period of several days. Moreover, the similarity of neural representations for good objects increased after learning, an outcome positively correlated with the habitual seeking response for good objects.
“These findings suggest that the ventral striatum plays a role in automatic evaluations of objects based on the neural representation of positive values retained since learning, to guide habitual seeking behaviors,” explained Professor Lee.
“We will fully investigate the function of different parts of the entire basal ganglia including the ventral striatum. We also expect that this understanding may lead to the development of better treatment for mental illnesses related to habitual behaviors or addiction problems.”
This study, supported by the National Research Foundation of Korea, was reported at Nature Communications (https://doi.org/10.1038/s41467-021-22335-5.)
-ProfileProfessor Sue-Hyun LeeDepartment of Bio and Brain EngineeringMemory and Cognition Laboratoryhttp://memory.kaist.ac.kr/lecture
KAIST
2021.06.03 View 5013 -
Identification of How Chemotherapy Drug Works Could Deliver Personalized Cancer Treatment
The chemotherapy drug decitabine is commonly used to treat patients with blood cancers, but its response rate is somewhat low. Researchers have now identified why this is the case, opening the door to more personalized cancer therapies for those with these types of cancers, and perhaps further afield.
Researchers have identified the genetic and molecular mechanisms within cells that make the chemotherapy drug decitabine—used to treat patients with myelodysplastic syndrome (MDS) and acute myeloid leukemia (AML) —work for some patients but not others. The findings should assist clinicians in developing more patient-specific treatment strategies.
The findings were published in the Proceedings of the National Academies of Science on March 30.
The chemotherapy drug decitabine, also known by its brand name Dacogen, works by modifying our DNA that in turn switches on genes that stop the cancer cells from growing and replicating. However, decitabine’s response rate is somewhat low (showing improvement in just 30-35% of patients), which leaves something of a mystery as to why it works well for some patients but not for others. To find out why this happens, researchers from the KAIST investigated the molecular mediators that are involved with regulating the effects of the drug.
Decitabine works to activate the production of endogenous retroviruses (ERVs), which in turn induces an immune response. ERVs are viruses that long ago inserted dormant copies of themselves into the human genome. Decitabine in essence, ‘reactivates’ these viral elements and produces double-stranded RNAs (dsRNAs) that the immune system views as a foreign body.
“However, the mechanisms involved in this process, in particular how production and transport of these ERV dsRNAs were regulated within the cell were understudied,” said corresponding author Yoosik Kim, professor in the Department of Chemical and Biomolecular Engineering at KAIST.
“So to explain why decitabine works in some patients but not others, we investigated what these molecular mechanisms were,” added Kim.
To do so, the researchers used image-based RNA interference (RNAi) screening. This is a relatively new technique in which specific sequences within a genome are knocked out of action or “downregulated.” Large-scale screening, which can be performed in cultured cells or within live organisms, works to investigate the function of different genes. The KAIST researchers collaborated with the Institut Pasteur Korea to analyze the effect of downregulating genes that recognize ERV dsRNAs and could be involved in the cellular response to decitabine.
From these initial screening results, they performed an even more detailed downregulation screening analysis. Through the screening, they were able to identify two particular gene sequences involved in the production of an RNA-binding protein called Staufen1 and the production of a strand of RNA that does not in turn produce any proteins called TINCR that play a key regulatory role in response to the drug. Staufen1 binds directly to dsRNAs and stabilizes them in concert with the TINCR.
If a patient is not producing sufficient Staufen1 and TINCR, then the dsRNA viral mimics quickly degrade before the immune system can spot them. And, crucially for cancer therapy, this means that patients with lower expression (activation) of these sequences will show inferior response to decitabine. Indeed, the researchers confirmed that MDS/AML patients with low Staufen1 and TINCR expression did not benefit from decitabine therapy.
“We can now isolate patients who will not benefit from the therapy and direct them to a different type of therapy,” said first author Yongsuk Ku. “This serves as an important step toward developing a patient-specific treatment cancer strategy.”
As the researchers used patient samples taken from bone marrow, the next step will be to try to develop a testing method that can identify the problem from just blood samples, which are much easier to acquire from patients.
The team plans to investigate if the analysis can be extended to patients with solid tumors in addition to those with blood cancers.
-Profile
Professor Yoosik Kim
https://qcbio.kaist.ac.kr/
Department of Chemical and Biomolecular Engineering
KAIST
-Publication
Noncanonical immune response to the inhibition of DNA methylation by Staufen1 via stabilization of endogenous retrovirus RNAs, PNAS
2021.05.24 View 5079 -
Dr. Won-Joon Lee from the ADD Wins the Jeong Hun Cho Award
Dr. Won-Joon Lee from the Agency for Defense Development (ADD) became the 17th Jeong Hun Cho Award recipient. KAIST PhD candidate Sok-Min Choi from the Department of Aerospace Engineering, Master’s-PhD combined course student Hyong-Won Choi from Korea University, and Chong-Ho Park from Kongju National University High School were also selected.
The award recognizes promising young scientists who makes significant achievements in the field of aerospace engineering in honor of Jeong Hun Cho, the former PhD candidate in the Department of Aerospace Engineering who died in a lab accident in May in 2003. Cho’s family endowed the award and scholarship to honor him. Three scholarship recipients from Cho’s alma mater, KAIST, Korea University, and Kongju National High School are selected every year.
Dr. Lee from the ADD has conducted research on shape design methods and radar absorbing structures for unmanned aerial vehicles, publishing more than 24 articles in SCI-level journals and 17 at academic conferences.
Dr. Lee was awarded 25 million KRW in prize money. The two students from KAIST and Korea University each received a 4 million KRW scholarship and Park received 3 million KRW.
2021.05.17 View 2615 -
Prof. Sang Yup Lee Elected as a Foreign Member of the Royal Society
Vice President for Research Distinguished Professor Sang Yup Lee was elected as a foreign member of the Royal Society in the UK. On May 6, the Society announced the list of distinguished new 52 fellows and 10 foreign members who achieved exceptional contributions to science. Professor Lee and Professor V. Narry Kim from Seoul National University are the first foreign members ever elected from Korea.
The Royal Society, established in 1660, is one of the most prestigious national science academies and a fellowship of 1,600 of the world’s most eminent scientists. From Newton to Darwin, Einstein, Hawking, and beyond, pioneers and paragons in their fields are elected by their peers. To date, there are 280 Nobel prize winners among the fellows.
Distinguished Professor Lee from the Department of Chemical and Biomolecular Engineering at KAIST is one of the Highly Cited Researchers (HCRs) who pioneered systems metabolic engineering and developed various micro-organisms for producing a wide range of fuels, chemicals, materials, and natural compounds.
His seminal scholarship and research career have already been recognized worldwide. He is the first Korean ever elected into the National Academy of Inventors (NAI) in the US and one of 13 scholars elected as an International Member of both the National Academy of Sciences (NAS) and the National Academy of Engineering (NAE) in the US. With this fellowship, he added one more accolade of being the first non-US and British Commonwealth scientist elected into the three most prestigious science academies: the NAS, the NAE, and the Royal Society.
2021.05.07 View 5721 -
Professor Byungha Shin Named Scientist of the Month
Professor Byungha Shin from the Department of Materials Science and Engineering won the Scientist of the Month Award presented by the Ministry of Science and ICT (MSIT) and the National Research Foundation of Korea (NRF) on May 4. Professor Shin was recognized for his research in the field of next-generation perovskite solar cells and received 10 million won in prize money.
To achieve ‘carbon neutrality,’ which many countries across the globe including Korea hope to realize, the efficiency of converting renewable energies to electricity must be improved. Solar cells convert solar energy to electricity. Since single solar cells show lower efficiency, the development of ‘tandem solar cells’ that connect two or more cells together has been popular in recent years.
However, although ‘perovskite’ received attention as a next-generation material for tandem solar cells, it is sensitive to the external environment including light and moisture, making it difficult to maintain stability.
Professor Shin discovered that, theoretically, adding certain anion additives to perovskite solar cells would allow the control of the electrical and structural properties of the two-dimensional stabilization layer that forms inside the film. He confirmed this through high-resolution transmission electron microscopy. Controlling the amount of anions in the additives allowed the preservation of over 80% of the initial stability even after 1000 hours of continuous exposure to sunlight.
Based on this discovery, Professor Shin combined silicon with solar cells to create a tandem solar cell with 26.7% energy convergence efficiency. Considering that the highest-efficiency tandem solar cell in existence showed 29.5% efficiency, this figure is quite high. Professor Shin’s perovskite solar cell is also combinable with the CIGS (Cu(In,Ga)Se2) thin-film solar cell composed of copper (Cu), indium (In), gallium (Ga), and selenium (Se2).
Professor Shin’s research results were published in the online edition of the journal Science in April of last year.
“This research is meaningful for having suggested a direction for solar cell material stabilization using additives,” said Professor Shin. “I look forward to this technique being applied to a wide range of photoelectrical devices including solar cells, LEDs, and photodetectors,” he added.
(END)
2021.05.07 View 4834 -
T-GPS Processes a Graph with Trillion Edges on a Single Computer
Trillion-scale graph processing simulation on a single computer presents a new concept of graph processing
A KAIST research team has developed a new technology that enables to process a large-scale graph algorithm without storing the graph in the main memory or on disks. Named as T-GPS (Trillion-scale Graph Processing Simulation) by the developer Professor Min-Soo Kim from the School of Computing at KAIST, it can process a graph with one trillion edges using a single computer.
Graphs are widely used to represent and analyze real-world objects in many domains such as social networks, business intelligence, biology, and neuroscience. As the number of graph applications increases rapidly, developing and testing new graph algorithms is becoming more important than ever before. Nowadays, many industrial applications require a graph algorithm to process a large-scale graph (e.g., one trillion edges). So, when developing and testing graph algorithms such for a large-scale graph, a synthetic graph is usually used instead of a real graph. This is because sharing and utilizing large-scale real graphs is very limited due to their being proprietary or being practically impossible to collect.
Conventionally, developing and testing graph algorithms is done via the following two-step approach: generating and storing a graph and executing an algorithm on the graph using a graph processing engine.
The first step generates a synthetic graph and stores it on disks. The synthetic graph is usually generated by either parameter-based generation methods or graph upscaling methods. The former extracts a small number of parameters that can capture some properties of a given real graph and generates the synthetic graph with the parameters. The latter upscales a given real graph to a larger one so as to preserve the properties of the original real graph as much as possible.
The second step loads the stored graph into the main memory of the graph processing engine such as Apache GraphX and executes a given graph algorithm on the engine. Since the size of the graph is too large to fit in the main memory of a single computer, the graph engine typically runs on a cluster of several tens or hundreds of computers. Therefore, the cost of the conventional two-step approach is very high.
The research team solved the problem of the conventional two-step approach. It does not generate and store a large-scale synthetic graph. Instead, it just loads the initial small real graph into main memory. Then, T-GPS processes a graph algorithm on the small real graph as if the large-scale synthetic graph that should be generated from the real graph exists in main memory. After the algorithm is done, T-GPS returns the exactly same result as the conventional two-step approach.
The key idea of T-GPS is generating only the part of the synthetic graph that the algorithm needs to access on the fly and modifying the graph processing engine to recognize the part generated on the fly as the part of the synthetic graph actually generated.
The research team showed that T-GPS can process a graph of 1 trillion edges using a single computer, while the conventional two-step approach can only process of a graph of 1 billion edges using a cluster of eleven computers of the same specification. Thus, T-GPS outperforms the conventional approach by 10,000 times in terms of computing resources. The team also showed that the speed of processing an algorithm in T-GPS is up to 43 times faster than the conventional approach. This is because T-GPS has no network communication overhead, while the conventional approach has a lot of communication overhead among computers.
Professor Kim believes that this work will have a large impact on the IT industry where almost every area utilizes graph data, adding, “T-GPS can significantly increase both the scale and efficiency of developing a new graph algorithm.”
This work was supported by the National Research Foundation (NRF) of Korea and Institute of Information & communications Technology Planning & Evaluation (IITP).
Publication:
Park, H., et al. (2021) “Trillion-scale Graph Processing Simulation based on Top-Down Graph Upscaling,” Presented at the IEEE ICDE 2021 (April 19-22, 2021, Chania, Greece)
Profile:
Min-Soo Kim
Associate Professor
minsoo.k@kaist.ac.kr
http://infolab.kaist.ac.kr
School of Computing
KAIST
2021.05.06 View 4540 -
Distinguished Professor Sang Yup Lee Honored with Charles D. Scott Award
Vice President for Research Sang Yup Lee received the 2021 Charles D. Scott Award from the Society for Industrial Microbiology and Biotechnology. Distinguished Professor Lee from the Department of Chemical and Biomolecular Engineering at KAIST is the first Asian awardee.
The Charles D. Scott Award, initiated in 1995, recognizes individuals who have made significant contributions to enable and further the use of biotechnology to produce fuels and chemicals. The award is named in honor of Dr. Charles D. Scott, who founded the Symposium on Biomaterials, Fuels, and Chemicals and chaired the conference for its first ten years.
Professor Lee has pioneered systems metabolic engineering and developed various micro-organisms capable of producing a wide range of fuels, chemicals, materials, and natural compounds, many of them for the first time. Some of the breakthroughs include the microbial production of gasoline, diacids, diamines, PLA and PLGA polymers, and several natural products.
More recently, his team has developed a microbial strain capable of the mass production of succinic acid, a monomer for manufacturing polyester, with the highest production efficiency to date, as well as a Corynebacterium glutamicum strain capable of producing high-level glutaric acid. They also engineered for the first time a bacterium capable of producing carminic acid, a natural red colorant that is widely used for food and cosmetics.
Professor Lee is one of the Highly Cited Researchers (HCR), ranked in the top 1% by citations in their field by Clarivate Analytics for four consecutive years from 2017. He is the first Korean fellow ever elected into the National Academy of Inventors in the US and one of 13 scholars elected as an International Member of both the National Academy of Sciences and the National Academy of Engineering in the USA.
The awards ceremony will take place during the Symposium on Biomaterials, Fuels, and Chemicals held online from April 26.
2021.04.27 View 4909